×

zbMATH — the first resource for mathematics

Neighbor sum distinguishing total chromatic number of \(K_4\)-minor free graph. (English) Zbl 1371.05097
Summary: A \(k\)-total coloring of a graph \(G\) is a mapping \(\phi: V(G) \cup E(G)\to\{1,2,\dots,k\}\) such that no two adjacent or incident elements in \(V(G)\cup E(G)\) receive the same color. Let \(f(v)\) denote the sum of the color on the vertex \(v\) and the colors on all edges incident with \(v\). We say that \(\phi\) is a \(k\)-neighbor sum distinguishing total coloring of \(G\) if \(f(u)\neq f(v)\) for each edge \(uv\in E(G)\). Denote \(\chi''_\Sigma(G)\) the smallest value \(k\) in such a coloring of \(G\). Pilśniak and Woźniak conjectured that for any simple graph with maximum degree \(\Delta(G)\), \(\chi''_\Sigma(G)\leqslant\Delta(G)+3\). In this paper, by using the famous Combinatorial Nullstellensatz, we prove that for \(K_4\)-minor free graph \(G\) with \(\Delta(G)\geqslant5\), \(\chi''_\Sigma(G)=\Delta(G)+1\) if \(G\) contains no two adjacent \(\Delta\)-vertices, otherwise, \(\chi''_\Sigma(G)=\Delta(G)+2\).

MSC:
05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alon, N, Combinatorial nullstellensatz, Combin Probab Comput, 8, 7-29, (1999) · Zbl 0920.05026
[2] Bondy J, Murty U. Graph Theory with Applications. New York: North-Holland,1976 · Zbl 1226.05083
[3] Cheng, X; Huang, D; Wang, G; Wu, J, Neighbor sum distinguishing total colorings of planar graphs with maximum degree, Discrete Appl Math, 190-191, 34-41, (2015) · Zbl 1316.05041
[4] Ding, L; Wang, G; Yan, G, Neighbour sum distinguishing total colorings via the combinatorial nullstellensatz, Sci China Math, 57, 1875-1882, (2014) · Zbl 1303.05058
[5] Dong, A; Wang, G, Neighbor sum distinguishing total colorings of graphs with bounded maximum average degree, Acta Math Sin (Engl Ser), 30, 703-709, (2014) · Zbl 1408.05061
[6] Li, H; Ding, L; Liu, B; Wang, G, Neighbor sum distinguishing total colorings of planar graphs, J Comb Optim, 30, 675-688, (2015) · Zbl 1325.05083
[7] Li, H; Liu, B; Wang, G, Neighbor sum distinguishing total colorings of K4-minor free graphs, Front Math China, 8, 1351-1366, (2013) · Zbl 1306.05066
[8] Pilśniak M, Woźniak M. On the adjacent-vertex-distinguishing index by sums in total proper colorings. http://www.ii.ui.edu.pl/preMD/index.php,2011
[9] Przybylo, J, Neighbour sum distinguishing total colorings via the combinatorial nullstellensatz, Discrete Appl Math, 202, 163-173, (2016) · Zbl 1330.05074
[10] Qu, C; Wang, G; Wu, J; Yu, X, On the neighbour sum distinguishing total coloring of planar graphs, Theoret Comput Sci, 609, 162-170, (2016) · Zbl 1331.05084
[11] Qu, C; Wang, G; Yan, G; Yu, X, Neighbor sum distinguishing total choosability of planar graphs, J Comb Optim, 32, 906-916, (2016) · Zbl 1348.05082
[12] Wang, J; Ma, Q; Han, X, Neighbor sum distinguishing total colorings of triangle free planar graphs, Acta Math Sin (Engl Ser), 31, 216-224, (2015) · Zbl 1317.05065
[13] Wang, J; Ma, Q; Han, X; Wang, X, A proper total coloring distinguishing adjacent vertices by sums of planar graphs without intersecting triangles, J Comb Optim, 32, 626-638, (2016) · Zbl 1343.05066
[14] Yao, J; Shao, Z; Xu, C, Neighbor sum distinguishing total choosability of graphs with δ = 3, Adv Math (China), 45, 343-348, (2016) · Zbl 1363.05087
[15] Yao, J; Xu, C, Neighbour sum distinguishing total coloring of graphs with maximum degree 3 or 4, J Shandong Univ Nat Sci, 50, 9-13, (2015)
[16] Yao, J; Yu, X; Wang, G; Xu, C, Neighbour sum (set) distinguishing total choosability of d-degenerate graphs, Graphs Combin, 32, 1611-1620, (2016) · Zbl 1342.05052
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.