Abstract
A total [k]-coloring of a graph \(G\) is a mapping \(\phi : V (G) \cup E(G)\rightarrow [k]=\{1, 2,\ldots , k\}\) such that any two adjacent or incident 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 \(uv\in E(G)\), \(f(u)\ne f(v)\). By \(\chi ^{''}_{nsd}(G)\), we denote the smallest value \(k\) in such a coloring of \(G\). Pilśniak and Wo��niak conjectured \(\chi _{nsd}^{''}(G)\le \Delta (G)+3\) for any simple graph with maximum degree \(\Delta (G)\). In this paper, we prove that this conjecture holds for any planar graph with maximum degree at least 13.
Similar content being viewed by others
References
Bondy JA, Murty USR (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
Ding L, Wang G, Yan G Neighbor sum distinguishing total colorings via the Combinatorial Nullstellensatz (submitted)
Ding L, Wang, G Neighbor sum distinguishing total colorings via the combinatorial Nullstellensatz revisited (submitted)
Dong A, Wang G Neighbor sum distinguishing total colorings of graphs with bounded maximum average degree. Acta Math Sin (to appear)
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)
Hulgan J (2009) Concise proofs for adjacent vertex-distinguishing total colorings. Discret Math 309:2548–2550
Huang P, Wong T, Zhu X (2012) Weighted-1-antimagic graphs of prime power order. Discret Math 312(14):2162–2169
Kalkowski M, Karoński M, Pfender F (2010) Vertex-coloring edge-weightings: towards the 1–2–3-conjecture. J Comb Theory Ser B 100:347–349
Karoński M, Łuczak T, Thomason A (2004) Edge weights and vertex colours. J Comb Theory Ser B 91(1):151–157
Li H, Liu B, Wang G (2013) Neighor sum distinguishing total colorings of \(K_4\)-minor free graphs. Front Math China. doi:10.1007/s11464-013-0322-x
Pilśniak M, Woźniak M (2011) On the adjacent-vertex-distinguishing index by sums in total proper colorings, Preprint MD 051. http://www.ii.uj.edu.pl/preMD/index.php
Przybyło J (2008) Irregularity strength of regular graphs. Electron J Comb 15(1):R82
Przybyło J (2009) Linear bound on the irregularity strength and the total vertex irregularity strength of graphs. SIAM J Discret Math 23(1):511–516
Przybyło J, Woźniak M (2011) Total weight choosability of graphs. Electron J Combin 18:P112
Przybyło J, Woźniak M (2010) On a 1,2 conjecture. Discret Math Theor Comput Sci 12(1):101–108
Seamone B The 1–2–3 conjecture and related problems: a survey. arXiv:1211.5122
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 (2012) The adjacent vertex distinguishing total coloring of planar graphs. J Comb Optim. doi:10.1007/s10878-012-9527-2
Wang W, Wang P (2009) On adjacent-vertex- distinguishing total coloring of \(K_4\)-minor free graphs. Sci China Ser A Math 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 Math 48(3):289–299
Wong T, Zhu X (2011) Total weight choosability of graphs. J Graph Theory 66:198–212
Wong T, Zhu X (2012) Antimagic labelling of vertex weighted graphs. J Graph Theory 3(70):348–350
Acknowledgments
This work was supported by the National Natural Science Foundation of China (11101243,61373027), the Research Fund for the Doctoral Program of Higher Education of China (20100131120017) and the Scientific Research Foundation for the Excellent Middle-Aged and Young Scientists of Shandong Province of China (BS2012SF016).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Li, H., Ding, L., Liu, B. et al. Neighbor sum distinguishing total colorings of planar graphs. J Comb Optim 30, 675–688 (2015). https://doi.org/10.1007/s10878-013-9660-6
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-013-9660-6