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.

05C15 Coloring of graphs and hypergraphs
05C78 Graph labelling (graceful graphs, bandwidth, etc.)
Full Text: DOI
[1] Behzad M. Graphs and Their Chromatic Numbers. Doctoral Thesis. East Lansing: Michigan State University, 1965
[2] Bondy J A, Murty U S R. Graph Theory with Applications. New York: North-Holland, 1976 · Zbl 1226.05083
[3] 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
[4] 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
[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 · Zbl 0871.05023 · doi:10.1016/0012-365X(95)00286-6
[6] Molloy M, Reed B. A bound on the total chromatic number. Combinatorics, 1998, 18: 241–280 · Zbl 0921.05033 · doi:10.1007/PL00009820
[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 · Zbl 1312.05054
[8] Rosenfeld M. On the total coloring of certain graphs. Israel J Math, 1971, 9: 396–402 · Zbl 0211.56604 · doi:10.1007/BF02771690
[9] 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
[10] Vizing V G. Some unsolved problems in graph theory. Uspehi Mat Nauk, 1968, 23: 117–134 · Zbl 0177.52301
[11] 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
[12] 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
[13] 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
[14] 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
[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 · 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.