Neighbor sum distinguishing total colorings of planar graphs

详细信息    查看全文

• 作者：Hualong Li ; Laihao Ding ; Bingqiang Liu…
• 关键词：Neighbor sum distinguishing total coloring ; Planar graph ; Maximum degree
• 刊名：Journal of Combinatorial Optimization
• 出版年：2015
• 出版时间：October 2015
• 年：2015
• 卷：30
• 期：3
• 页码：675-688
• 全文大小：472 KB
• 参考文献：Bondy JA, Murty USR (1976) Graph theory with applications. North-Holland, New YorkMATH
  Chen X (2008) On the adjacent vertex distinguishing total coloring numbers of graphs with \(\Delta = 3\) . Discret Math 308(17):4003-007CrossRef MATH
  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-64 (in Chinese)CrossRef
  Hulgan J (2009) Concise proofs for adjacent vertex-distinguishing total colorings. Discret Math 309:2548-550MathSciNet CrossRef MATH
  Huang P, Wong T, Zhu X (2012) Weighted-1-antimagic graphs of prime power order. Discret Math 312(14):2162-169MathSciNet CrossRef MATH
  Kalkowski M, Karoński M, Pfender F (2010) Vertex-coloring edge-weightings: towards the 1---conjecture. J Comb Theory Ser B 100:347-49CrossRef MATH
  Karoński M, ?uczak T, Thomason A (2004) Edge weights and vertex colours. J Comb Theory Ser B 91(1):151-57CrossRef MATH
  Li H, Liu B, Wang G (2013) Neighor sum distinguishing total colorings of \(K_4\) -minor free graphs. Front Math China. doi:10.-007/?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-16CrossRef
  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-08MATH
  Seamone B The 1-- 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-09MathSciNet CrossRef MATH
  Wang W, Huang D (2012) The adjacent vertex distinguishing total coloring of planar graphs. J Comb Optim. doi:10.-007/?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-472
  Wang Y, Wang W (2010) Adjacent vertex distinguishing total colorings of outerplanar graphs. J Comb Optim 19:123-33MathSciNet CrossRef MATH
  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-99MathSciNet CrossRef MATH
  Wong T, Zhu X (2011) Total weight choosability of graphs. J Graph Theory 66:198-12MathSciNet CrossRef MATH
  Wong T, Zhu X (2012) Antimagic labelling of vertex weighted graphs. J Graph Theory 3(70):348-50MathSciNet CrossRef
  
• 作者单位：Hualong Li (1)
  Laihao Ding (1)
  Bingqiang Liu (1)
  Guanghui Wang (1)
  
  1. School of Mathematics, Shandong University, Jinan?, 250100, Shandong, People’s Republic of China
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Convex and Discrete Geometry
  Mathematical Modeling and IndustrialMathematics
  Theory of Computation
  Optimization
  Operation Research and Decision Theory
  
• 出版者：Springer Netherlands
• ISSN：1573-2886

文摘

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. Keywords Neighbor sum distinguishing total coloring Planar graph Maximum degree