zbMATH — the first resource for mathematics

Neighbor sum distinguishing total colorings of planar graphs with maximum degree \(\varDelta\). (English) Zbl 1316.05041
Summary: A (proper) total [k]-coloring of a graph \(G\) is a mapping \(\phi : V(G) \cup E(G) \to [k] = \{1, 2, \ldots, k \}\) such that any two adjacent elements in \(V(G) \cup E(G)\) receive different colors. Let \(f(v)\) denote the sum of the color 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 \(u v \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\). In this paper, we show that if \(G\) is a planar graph with \(\varDelta(G) \geq 14\), then \(\chi_{\mathrm{nsd}}^{\prime\prime}(G) \leq \varDelta(G) + 2\).

05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
05C07 Vertex degrees
05C35 Extremal problems in graph theory
Full Text: DOI
[1] Bondy, J. A.; Murty, U. S.R., Graph theory with applications, (1976), North-Holland New York · Zbl 1134.05001
[2] Ding, L.; Wang, H.; Yan, G., Neighbor sum distinguishing total colorings via the combinatorial nullstellensatz, Sci. China Math., 57, 1875-1882, (2014) · Zbl 1303.05058
[3] Dong, A.; Wang, G., Neighbor sum distinguishing total colorings of graphs with bounded maximum average degree, Acta Math. Sin. (Engl. Ser.), 30, 4, 703-709, (2014) · Zbl 1408.05061
[4] H. Li, L. Ding, B. Liu, G. Wang, Neighbor sum distinguishing total colorings of planar graphs, J. Comb. Optim. http://dx.doi.org/10.1007/s10878-013-9660-6. · Zbl 1325.05083
[5] 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
[6] M. Pilśniak, M. Woźniak, On the Total-Neighbor-Distinguishing Index by Sums, Graphs and Combinatorics, http://dx.doi.org/10.1007/s00373-013-1399-4.
[7] Wang, W.; Huang, D., The adjacent vertex distinguishing total coloring of planar graphs, J. Comb. Optim., 27, 2, 379-396, (2014) · Zbl 1319.90076
[8] Zhang, Z.; Chen, X.; Li, J.; Yao, B.; Lu, X.; Wang, J., On adjacent-vertex- distinguishing total coloring of graphs, Sci. China 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.