zbMATH — the first resource for mathematics

Neighbor sum distinguishing total chromatic number of planar graphs. (English) Zbl 1427.05093
Summary: Let $$G = (V(G), E(G))$$ be a graph and $$\phi$$ be a proper $$k$$-total coloring of $$G$$. Set $$f_\phi(v) = \sum_{u v \in E(G)} \phi(u v) + \phi(v)$$, for each $$v \in V(G)$$. If $$f_\phi(u) \neq f_\phi (v)$$ for each edge $$uv \in E(G)$$, the coloring $$\phi$$ is called a $$k$$-neighbor sum distinguishing total coloring of $$G$$. The smallest integer $$k$$ in such a coloring of $$G$$ is the neighbor sum distinguishing total chromatic number, denoted by $$\chi_\Sigma''(G)$$. In this paper, by using the famous Combinatorial Nullstellensatz, we determine $$\chi_\Sigma''(G)$$ for any planar graph $$G$$ with $$\Delta (G) \geq 13$$.

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, Comb. Probab. Comput., 8, 7-29 (1999) · Zbl 0920.05026 [2] Bondy, J.; Murty, U., Graph Theory with Applications (1976), New York, North-Holland · 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] Cheng, X.; Wang, G.; Wu, J., The adjacent vertex distinguishing total chromatic numbers of planar graphs with $$\Delta = 10$$, J. Comb. Optim., 34, 2, 383-397 (2017) · Zbl 1376.05052 [5] Dong, A.; Wang, G., Neighbor sum distinguishing total colorings of graphs with bounded maximum average degree, Acta. Math. Sin., 30, 4, 703-709 (2014) · Zbl 1408.05061 [6] 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 [8] Huang, D.; Wang, W., Adjacent vertex distinguishing total coloring of planar graphs with large maximum degree, Sci. Sin. Math, 42, 2, 151-164 (2012) [9] Li, H.; Ding, L.; Liu, B.; Wang, G., Neighbor sum distinguishing total colorings of planar graphs, J. Comb. Optim., 30, 3, 675-688 (2015) · Zbl 1325.05083 [10] Li, J.; Ge, S.; Xu, C., Neighbor sum distinguishing total colorings of planar graphs with girth at least 5, Utilitas Math., 104, 115-121 (2017) · Zbl 1383.05108 [11] Ma, Q.; Wang, J.; Zhao, H., Neighbor sum distinguishing total colorings of planar graphs without short cycles, Utilitas Math., 98, 349-359 (2015) · Zbl 1342.05045 [12] Pilśniak, M.; Woźniak, M., On the total-neighbor-distinguishing index by sums, Graphs Combin., 31, 3, 771-782 (2015) · Zbl 1312.05054 [13] Qu, C.; Wang, G.; Wu, J.; Yu, X., On the neighbor sum distinguishing total coloring of planar graphs, Theoret. Comput. Sci., 609, 162-170 (2016) · Zbl 1331.05084 [14] Qu, C.; Wang, G.; Yan, G.; Yu, X., Neighbor sum distinguishing total choosability of planar graphs, J. Comb. Optim., 32, 3, 906-916 (2016) · Zbl 1348.05082 [15] Song, H.; Pan, W.; Gong, X.; Xu, C., A note on the neighbor sum distinguishing total coloring of planar graphs, Theoret. Comput. Sci., 640, 125-129 (2016) · Zbl 1345.05035 [16] Song, H.; Xu, C., Neighbor sum distinguishing total chromatic number of $$K_4$$-minor free graph, Front. Math. China, 12, 4, 937-947 (2017) · Zbl 1371.05097 [17] Song, H.; Xu, C., Neighbor sum distinguishing total coloring of planar graphs without 4-cycles, J. Comb. Optim., 34, 1147-1158 (2017) · Zbl 1378.05073 [18] 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 [19] Wang, J.; Cai, J.; Qiu, B., Neighbor sum distinguishing total choosability of planar graphs without adjacent triangles, Theoret. Comput. Sci., 661, 1-7 (2017) · Zbl 1357.05027 [20] Wang, J.; Ma, Q.; Han, X., Neighbor sum distinguishing total colorings of triangle free planar graphs, Acta Math. Sin. Engl. Series, 31, 2, 216-224 (2015) · Zbl 1317.05065 [22] Yang, D.; Yu, X.; Sun, L.; Wu, J.; Zhou, S., Neighbor sum distinguishing total chromatic number of planar graphs with maximum degree 10, Appl. Math. Comput., 314, 456-468 (2017) · Zbl 1426.05051 [23] Yao, J.; Yu, X.; Wang, G.; Xu, C., Neighbor sum distinguishing total coloring of 2-degenerate graphs, J. Comb. Optim., 34, 1, 64-70 (2017) · Zbl 1394.05037 [24] Yao, J.; Yu, X.; Wang, G.; Xu, C., Neighbor sum (set) distinguishing total choosability of $$d$$-degenerate graphs, Graphs Comb., 32, 4, 1611-1620 (2016) · Zbl 1342.05052 [25] Zhang, Z.; Chen, X.; Li, J.; Yao, B.; Lu, X.; Wang, J., On adjacent-vertex-distinguishing total coloring of graphs, Sci. China Ser. A, 48, 3, 289-299 (2005) · Zbl 1080.05036
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.