On vertex-coloring edge-weighting of graphs

Abstract

A k-edge-weighting w of a graph G is an assignment of an integer weight, w(e) ∈ {1,…,k}, to each edge e. An edge-weighting naturally induces a vertex coloring c by defining c(u) = Σ_e∋uw(e) for every u ∈ V (G). A k-edge-weighting of a graph G is vertex-coloring if the induced coloring c is proper, i.e., c(u) ≠ c(v) for any edge uv ∈ E(G). When k ≡ 2 (mod 4) and k ⩾ 6, we prove that if G is k-colorable and 2-connected, δ(G) ⩾ k − 1, then G admits a vertex-coloring k-edge-weighting. We also obtain several sufficient conditions for graphs to be vertex-coloring k-edge-weighting.

Keywords

Vertex coloring / edge-weighting

References

[1] Addario-Berry L., Aldred R. E. L., Dalal K., Reed B. A. Vertex coloring edge partitions. J Combin Theory, 2005, 94: 237-244.

[2] Balister P. N., Riordan O. M., Schelp R. H. Vertex-distinguishing edge colorings of graphs. J Graph Theory, 2003, 42: 95-109.

[3] Bollobás B. Modern Graph Theory, 1998 2nd Ed. New York: Springer-Verlag.

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

[5] Wang T., Yu Q. On vertex-coloring 13-edge-weighting. Front Math China, 2008, 3(4): 581-587.