Neighbor sum distinguishing total colorings of K₄-minor free graphs

Abstract

A total [k]-coloring of a graph G is a mapping ϕ: V (G) ∪ E(G) → {1, 2, …, k} such that any two adjacent elements in V (G)∪E(G) receive different colors. Let f(v) denote the sum of the colors of a vertex v and the colors of all incident edges of v. A total [k]-neighbor sum distinguishing-coloring of G is a total [k]-coloring of G such that for each edge uv ∈ E(G), f(u) ≠ f(v). By χ_nsd″, we denote the smallest value k in such a coloring of G. Pilśniak and Woźniak conjectured χ_nsd″(G) ⩽ Δ(G)+3 for any simple graph with maximum degree Δ(G). This conjecture has been proved for complete graphs, cycles, bipartite graphs, and subcubic graphs. In this paper, we prove that it also holds for K₄-minor free graphs. Furthermore, we show that if G is a K₄-minor free graph with Δ(G) ⩾ 4, then gc_nsd″(G) ⩽ Δ(G) + 2. The bound Δ(G) + 2 is sharp.

Keywords

K₄-minor free graph / neighbor sum distinguishing (nsd)

References

[1] Behzad M. Graphs and Their Chromatic Numbers, 1965, East Lansing: Michigan State University

[2] Bondy J A, Murty U S R. Graph Theory with Applications, 1976, New York: North-Holland

[3] Chen X. On the adjacent vertex distinguishing total coloring numbers of graphs with Δ = 3. Discrete Math, 2008, 308: 4003-4007

[4] Dong A, Wang G. Neighbor sum distinguishing total colorings of graphs with bounded maximum average degree. Acta Math Sin (Engl Ser) (to appear)

[5] Kostochka A V. The total chromatic number of any multigraph with maximum degree five is at most seven. Discrete Math, 1996, 162: 199-214

[6] Molloy M, Reed B. A bound on the total chromatic number. Combinatorics, 1998, 18: 241-280

[7] Pilśniak M, Woźniak M. On the adjacent-vertex-distinguishing index by sums in total proper colorings. http://www.ii.uj.edu.pl/preMD/index.php

[8] Rosenfeld M. On the total coloring of certain graphs. Israel J Math, 1971, 9: 396-402

[9] Vijayaditya N. On total chromatic number of a graph. J Lond Math Soc (2), 1971, 3: 405-408

[10] Vizing V G. Some unsolved problems in graph theory. Uspehi Mat Nauk, 1968, 23: 117-134

[11] Wang H. On the adjacent vertex distinguishing total chromatic number of the graphs with Δ(G) = 3. J Comb Optim, 2007, 14: 87-109

[12] Wang W, Wang P. On adjacent-vertex-distinguishing total coloring of K₄-minor free graphs. Sci China Ser A, 2009, 39(12): 1462-1472

[13] Wang W, Wang Y. Adjacent vertex distinguishing edge colorings of K₄-minor free graph. Appl Math Lett, 2011, 24: 2034-2037

[14] Wang Y, Wang W. Adjacent vertex distinguishing total colorings of outerplanar graphs. J Comb Optim, 2010, 19: 123-133

[15] Zhang Z, Chen X, Li J, Yao B, Lu X, Wang J. On adjacent-vertex-distinguishing total coloring of graphs. Sci China Ser A, 2005, 48(3): 289-299