# zbMATH — the first resource for mathematics

Neighbor sum distinguishing total colorings of $$K_4$$-minor free graphs. (English) Zbl 1306.05066
Summary: A total $$[k]$$-coloring of a graph $$G$$ is a mapping $$\phi :V(G)\cup E(G) \to\{1, 2, \dots, k\}$$ such that any two adjacent elements in $$V(G)\cup 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\in E(G)$$, $$f(u)\neq f(v)$$. By $$\chi_{\mathrm{nsd}}^{\prime\prime}(G)$$, we denote the smallest value $$k$$ in such a coloring of G. Pilśniak and Woźniak conjectured $$\chi_{\mathrm{nsd}}^{\prime\prime} (G)\Delta (G)+3$$ for any simple graph with maximum degree $$\Delta (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 $$\Delta(G)\geqslant 4$$, then $$\chi_{\mathrm{nsd}}^{\prime\prime}(G)\leqslant \Delta (G)+2$$. The bound $$\Delta (G)+2$$ is sharp.

##### MSC:
 05C15 Coloring of graphs and hypergraphs 05C78 Graph labelling (graceful graphs, bandwidth, etc.)
##### Keywords:
$$K_4$$-minor free graph; neighbor sum distinguishing
Full Text:
##### 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 · Zbl 1226.05083  Chen X. On the adjacent vertex distinguishing total coloring numbers of graphs with $$\Delta$$ = 3. Discrete Math, 2008, 308: 4003–4007 · Zbl 1203.05052 · doi:10.1016/j.disc.2007.07.091  Dong A, Wang G. Neighbor sum distinguishing total colorings of graphs with bounded maximum average degree. Acta Math Sin (Engl Ser) (to appear) · Zbl 1408.05061  Kostochka A V. The total chromatic number of any multigraph with maximum degree five is at most seven. Discrete Math, 1996, 162: 199–214 · Zbl 0871.05023 · doi:10.1016/0012-365X(95)00286-6  Molloy M, Reed B. A bound on the total chromatic number. Combinatorics, 1998, 18: 241–280 · Zbl 0921.05033 · doi:10.1007/PL00009820  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 · Zbl 1312.05054  Rosenfeld M. On the total coloring of certain graphs. Israel J Math, 1971, 9: 396–402 · Zbl 0211.56604 · doi:10.1007/BF02771690  Vijayaditya N. On total chromatic number of a graph. J Lond Math Soc (2), 1971, 3: 405–408 · Zbl 0223.05103 · doi:10.1112/jlms/s2-3.3.405  Vizing V G. Some unsolved problems in graph theory. Uspehi Mat Nauk, 1968, 23: 117–134 · Zbl 0177.52301  Wang H. On the adjacent vertex distinguishing total chromatic number of the graphs with $$\Delta$$(G) = 3. J Comb Optim, 2007, 14: 87–109 · Zbl 1125.05043 · doi:10.1007/s10878-006-9038-0  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 · Zbl 1234.05105 · doi:10.1016/j.aml.2011.05.038  Wang Y, Wang W. Adjacent vertex distinguishing total colorings of outerplanar graphs. J Comb Optim, 2010, 19: 123–133 · Zbl 1216.05039 · doi:10.1007/s10878-008-9165-x  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 · Zbl 1080.05036 · doi:10.1360/03YS0207
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.