Abstract
A (proper) total-k-coloring of a graph G is a mapping \(\phi : V (G) \cup E(G)\mapsto \{1, 2, \ldots , k\}\) such that any two adjacent elements in \(V (G) \cup E(G)\) receive different colors. Let C(v) denote the set of the color of a vertex v and the colors of all incident edges of v. A total-k-adjacent vertex distinguishing-coloring of G is a total-k-coloring of G such that for each edge \(uv\in E(G)\), \(C(u)\ne C(v)\). We denote the smallest value k in such a coloring of G by \(\chi ''_{a}(G)\). It is known that \(\chi _{a}''(G)\le \Delta (G)+3\) for any planar graph with \(\Delta (G)\ge 11\). In this paper, we show that if G is a planar graph with \(\Delta (G)\ge 10\), then \(\chi _{a}''(G)\le \Delta (G)+3\). Our approach is based on Combinatorial Nullstellensatz and the discharging method.
We’re sorry, something doesn't seem to be working properly.
Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.
References
Alon N (1999) Combinatorial Nullstellensatz. Comb Probab Comput 8:7–29
Appel K, Haken W, Koch J (1977) Every planar graph map is four colorable. Part II: reducibility. Ill J Math 21:491–567
Appel K, Haken W (1977) Every planar graph map is four colorable. Part I: discharging. Ill J Math 21:429–490
Bondy J, Murty U (1976) Graph theory with applications. North-Holland, New York
Chen X (2008) On the adjacent vertex distinguishing total coloring numbers of graphs with \(\Delta = 3\). Discret Math 308(17):4003–4007
Cheng X, Huang D, Wang G, Wu J (2015) Neighbor sum distinguishing total colorings of planar graphs with maximum degree \(\Delta \). Discret Appl Math 190–191:34–41
Coker T, Johannson K (2012) The adjacent vertex distinguishing total chromatic number. Discret Math 312(17):2741–2750
Ding L, Wang G, Yan G (2014) Neighbor sum distinguishing total colorings via the Combinatorial Nullstellensatz. Sci Sin Math 57(9):1875–1882
Dong A, Wang G (2014) Neighbor sum distinguishing total colorings of graphs with bounded maximum average degree. Acta Math Sinica 30(4):703–709
Huang D, Wang W, Yan C (2012) A note on the adjacent vertex distinguishing total chromatic number of graphs. Discret Math 312(24):3544–3546
Huang D, Wang W (2012) Adjacent vertex distinguishing total coloring of planar graphs with large maximum degree. Sci Sin Math 42(2):151–164 (in Chinese)
Li H, Liu B, Wang G (2013) Neighbor sum distinguishing total colorings of \(K_4\)-minor free graphs. Front Math China 8(6):1351–1366
Li H, Ding L, Liu B, Wang G (2015) Neighbor sum distinguishing total colorings of planar graphs. J Comb Optim 30(3):675–688
Pilśniak M, Woźniak M (2015) On the total-neighbor-distinguishing index by sums. Graphs Comb 31(3):771–782
Sanders D, Zhao Y (2001) Planar graphs of maximum degree seven are class I. J Comb Theory B 83:201–212
Vizing V (1964) On an estimate of the chromatic index of a \(p\)-graph. Metody Diskret Analiz 3:25–30 (in Russian)
Wang H (2007) On the adjacent vertex distinguishing total chromatic number of the graphs with \(\Delta (G)=3\). J Comb Optim 14:87–109
Wang W, Huang D (2014) The adjacent vertex distinguishing total coloring of planar graphs. J Comb Optim 27(2):379–396
Wang W, Wang P (2009) On adjacent-vertex-distinguishing total coloring of \(K_4\)-minor free graphs. Sci China Ser A 39(12):1462–1472
Wang Y, Wang W (2010) Adjacent vertex distinguishing total colorings of outerplanar graphs. J Comb Optim 19:123–133
Zhang Z, Chen X, Li J, Yao B, Lu X, Wang J (2005) On adjacent-vertex-distinguishing total coloring of graphs. Sci China Ser A 48(3):289–299
Acknowledgments
This work was supported by the National Natural Science Foundation of China (11271006, 11371355, 11471193, 11501316), the Foundation for Distinguished Young Scholars of Shandong Province (JQ201501), the Shandong Provincial Natural Science Foundation of China (ZR2014AQ001), and the Independent Innovation Foundation of Shandong University (IFYT 14012, IFYT 14013).
Author information
Authors and Affiliations
Corresponding author
Appendix
Appendix
Rights and permissions
About this article
Cite this article
Cheng, X., Wang, G. & Wu, J. The adjacent vertex distinguishing total chromatic numbers of planar graphs with \(\Delta =10\) . J Comb Optim 34, 383–397 (2017). https://doi.org/10.1007/s10878-016-9995-x
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-016-9995-x