zbMATH — the first resource for mathematics

A note on the neighbor sum distinguishing total coloring of planar graphs. (English) Zbl 1345.05035
Summary: Let $$G = (V(G), E(G))$$ be a graph and $$\phi$$ be a proper total $$k$$-coloring of $$G$$. Let $$f(v)$$ denote the sum of the color on a vertex $$v$$ and colors on all the edges incident with $$v$$. $$\phi$$ is neighbor sum distinguishing if $$f(u) \neq f(v)$$ for each edge $$u v \in E(G)$$. The smallest integer $$k$$ for which such a coloring of $$G$$ exists is the neighbor sum distinguishing total chromatic number and denoted by $$\chi_{\Sigma}^{\prime\prime}(G)$$. M. Pilśniak and M. Woźniak [Graphs Comb. 31, No. 3, 771–782 (2015; Zbl 1312.05054)] conjectured that for any simple graph with maximum degree $$\Delta(G)$$, $$\chi_{\Sigma}^{\prime\prime}(G) \leq \Delta(G) + 3$$. It is known that for any simple planar graph, $$\chi_{\Sigma}^{\prime\prime}(G) \leq \max \{\Delta(G) + 3, 14 \}$$ and $$\chi_{\Sigma}^{\prime\prime}(G) \leq \max \{\Delta(G) + 2, 16 \}$$. In this paper, by using the famous Combinatorial Nullstellensatz, we show that for any simple planar graph, $$\chi_{\Sigma}^{\prime\prime}(G) \leq \max \{\Delta(G) + 2, 14 \}$$. The bound $$\Delta(G) + 2$$ is sharp.

MSC:
 05C15 Coloring of graphs and hypergraphs 05C10 Planar graphs; geometric and topological aspects of graph theory
Full Text:
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, (1976), North-Holland New York · Zbl 1226.05083 [3] Cheng, X.; Huang, D.; Wang, G., 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.; Yan, G., Neighbor sum distinguishing total colorings via the combinatorial nullstellensatz, Sci. China Math., 57, 9, 1875-1882, (2014) · Zbl 1303.05058 [5] Li, H.; Ding, L.; Liu, B., Neighbor sum distinguishing total colorings of planar graphs, J. Comb. Optim., 30, 3, 675-688, (2015) · Zbl 1325.05083 [6] Li, H.; Liu, B.; Wang, G., Neighbor sum distinguishing total colorings of $$K_4$$-minor free graphs, Front. Math. China, 8, 6, 1351-1366, (2013) · Zbl 1306.05066 [7] Pilśniak, M.; Woźniak, M., On the adjacent-vertex-distinguishing index by sums in total proper colorings, Graphs Combin., (2013) [8] Przybyło, J., Neighbour sum distinguishing total colorings via the combinatorial nullstellensatz, Discrete Appl. Math., 202, 163-173, (2016) · Zbl 1330.05074 [9] Qu, C.; Wang, G.; Wu, J., On the neighbor sum distinguishing total coloring of planar graphs, Theoret. Comput. Sci., 609, 162-170, (2016) · Zbl 1331.05084 [10] Qu, C.; Wang, G.; Yan, G., Neighbor sum distinguishing total choosability of planar graphs, J. Comb. Optim., (2015) [11] 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 [12] Wang, J.; Ma, Q.; Han, X., Neighbor sum distinguishing total colorings of triangle free planar graphs, Acta Math. Sin. (Engl. Ser.), 31, 2, 216-224, (2015) · Zbl 1317.05065 [13] Wang, J.; Ma, Q.; Han, X., A proper total coloring distinguishing adjacent vertices by sums of planar graphs without intersecting triangles, J. Comb. Optim., (2015) [14] Yao, J.; Shao, Z.; Xu, C., Neighbor sum distinguishing total choosability of graphs with $$\operatorname{\Delta} = 3$$, Adv. Math. (China), (2014) [15] Yao, J.; Yu, X.; Wang, G.; Xu, C., Neighbor sum (set) distinguishing total choosability of d-degenerate graphs, Graphs Combin., (2015)
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.