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 4-minor free graphs. Furthermore, we show that if G is a K 4-minor free graph with Δ(G) ⩾ 4, then gc nsd″(G) ⩽ Δ(G) + 2. The bound Δ(G) + 2 is sharp.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Behzad M. Graphs and Their Chromatic Numbers. Doctoral Thesis. East Lansing: Michigan State University, 1965
Bondy J A, Murty U S R. Graph Theory with Applications. New York: North-Holland, 1976
Chen X. On the adjacent vertex distinguishing total coloring numbers of graphs with Δ = 3. Discrete Math, 2008, 308: 4003–4007
Dong A, Wang G. Neighbor sum distinguishing total colorings of graphs with bounded maximum average degree. Acta Math Sin (Engl Ser) (to appear)
Kostochka A V. The total chromatic number of any multigraph with maximum degree five is at most seven. Discrete Math, 1996, 162: 199–214
Molloy M, Reed B. A bound on the total chromatic number. Combinatorics, 1998, 18: 241–280
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
Rosenfeld M. On the total coloring of certain graphs. Israel J Math, 1971, 9: 396–402
Vijayaditya N. On total chromatic number of a graph. J Lond Math Soc (2), 1971, 3: 405–408
Vizing V G. Some unsolved problems in graph theory. Uspehi Mat Nauk, 1968, 23: 117–134
Wang H. On the adjacent vertex distinguishing total chromatic number of the graphs with Δ(G) = 3. J Comb Optim, 2007, 14: 87–109
Wang W, Wang P. On adjacent-vertex-distinguishing total coloring of K 4-minor free graphs. Sci China Ser A, 2009, 39(12): 1462–1472
Wang W, Wang Y. Adjacent vertex distinguishing edge colorings of K 4-minor free graph. Appl Math Lett, 2011, 24: 2034–2037
Wang Y, Wang W. Adjacent vertex distinguishing total colorings of outerplanar graphs. J Comb Optim, 2010, 19: 123–133
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
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Li, H., Liu, B. & Wang, G. Neighbor sum distinguishing total colorings of K 4-minor free graphs. Front. Math. China 8, 1351–1366 (2013). https://doi.org/10.1007/s11464-013-0322-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11464-013-0322-x