On vertex-coloring 13-edge-weighting

Abstract

L. Addario-Berry et al. [Discrete Appl. Math., 2008, 156: 1168-1174] have shown that there exists a 16-edge-weighting such that the induced vertex coloring is proper. In this note, we improve their result and prove that there exists a 13-edge-weighting of a graph G, such that its induced vertex coloring of G is proper. This result is one step close to the original conjecture posed by M. Karoński et al.

Keywords

Vertex coloring / edge weighting / degree constrained subgraph

References

[1] Addario-Berry L., Dalal K., McDiarmid C., Reed B., Thomason A. Vertex-colouring edge-weightings. Combinatorica, 2007, 27: 1-12.

[2] Addario-Berry L., Dalal K., Reed B. Degree constrained subgraphs. Discrete Appl Math, 2008, 156: 1168-1174.

[3] Karoński M., Luczak T., Thomason A. Edge weights and vertex colours. J Combin Theory, 2004, 91: 151-157.