×

zbMATH — the first resource for mathematics

Neighbor sum distinguishing total coloring of planar graphs without 4-cycles. (English) Zbl 1378.05073
Summary: Let \(G=(V,E)\) be a graph and \(\phi:V\cup E\rightarrow \{1,2,\dots,k\}\) be a proper total coloring of \(G\). Let \(f(v)\) denote the sum of the color on a vertex \(v\) and the colors on all the edges incident with \(v\). The coloring \(\phi\) is neighbor sum distinguishing if \(f(u)\neq f(v)\) for each edge \(uv\in E(G)\). The smallest integer \(k\) in such a coloring of \(G\) is the neighbor sum distinguishing total chromatic number of \(G\), denoted by \(\chi^{\prime\prime}_\Sigma(G)\). M. Pilśniak and M. Woźniak [Graphs Comb. 31, No. 3, 771–782 (2015; Zbl 1312.05054)] conjectured that \(\chi^{\prime\prime}_\Sigma(G)\leq \Delta (G)+3\) for any simple graph. By using the famous Combinatorial Nullstellensatz, we prove that \(\chi^{\prime\prime}_\Sigma(G)\leq\max\{\Delta (G)+2,10\}\) for planar graph \(G\) without 4-cycles. The bound \(\Delta (G)+2\) is sharp if \(\Delta (G)\geq 8\).

MSC:
05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
PDF BibTeX Cite
Full Text: DOI
References:
[1] Alon, N, Combinatorial nullstellensatz, Comb Probab Comput, 8, 7-29, (1999) · Zbl 0920.05026
[2] Bondy J, Murty U (1976) Graph theory with applications. North-Holland, New York · 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, 34-41, (2015) · Zbl 1316.05041
[4] Ding L, Wang G, Wu J, Yu J (2014) Neighbor sum (set) distinguising total choosability via the Combinatorial Nullstellensatz (submitted) · Zbl 1345.05035
[5] 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
[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 \(K_{4}\)-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, Graphs Comb, (2013) · Zbl 1312.05054
[9] Przybyło, 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, Theor Comput Sci, 609, 162-170, (2016) · Zbl 1331.05084
[11] Qu C, Wang G, Yan G, Yu X (2016) Neighbor sum distinguishing total choosability of planar graphs. J Comb Optim 32(3):906-916 · Zbl 1348.05082
[12] Song, H; Pan, W; Gong, X; Xu, C, A note on the neighbor sum distinguishing total coloring of planar graphs, Theor Comput Sci, 640, 125-129, (2016) · Zbl 1345.05035
[13] Wang, J; Cai, J; Ma, Q, Neighbor sum distinguishing total choosability of planar graphs without 4-cycles, Discrete Appl Math, 206, 215-219, (2016) · Zbl 1335.05051
[14] Wang G, Ding L, Cheng X, Wu J Improved bounds for neighobr sum (set) distinguishing choosability of planar graphs. SIAM Discrete Math (submitted) · Zbl 1342.05052
[15] 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
[16] Wang J, Ma Q, Han X, Wang X (2016) A proper tatal coloring distinguishing adjacent vertices by sums of planar graphs without intersecting triangles. J Comb Optim 32(2):626-638 · Zbl 1343.05066
[17] Yao, J; Yu, X; Wang, G; Xu, C, Neighbor sum distinguishing total coloring of 2-degenerate graphs, J Comb Optim, (2016) · Zbl 1342.05052
[18] 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
[19] Yao, J; Yu, X; Wang, G; Xu, C, Neighbour sum (set) distinguishing total choosability of \(d\)-degenerate graphs, Graphs Comb, 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.