The \(r\) -acyclic chromatic number of planar graphs

详细信息    查看全文

• 作者：Guanghui Wang (1)
  Guiying Yan (2)
  Jiguo Yu (3)
  Xin Zhang (4)
  
  1. School of Mathematics ; Shandong University ; Jinan ; 250100 ; Shandong ; People鈥檚 Republic of China
  2. Academy of Mathematics and System Sciences ; Chinese Academy of Sciences ; Beijing ; 10080 ; People鈥檚 Republic of China
  3. School of Computer Science ; Qufu Normal University ; Rizhao ; 276826 ; Shandong ; People鈥檚 Republic of China
  4. Department of Mathematics ; Xidian University ; Xian ; 710071 ; Shaanxi ; People鈥檚 Republic of China
  
• 关键词：Acyclic coloring ; Planar graph ; Girth
• 刊名：Journal of Combinatorial Optimization
• 出版年：2015
• 出版时间：May 2015
• 年：2015
• 卷：29
• 期：4
• 页码：713-722
• 全文大小：175 KB
• 参考文献：1. Agnarsson, G, Halld贸rsson, MM (2003) Coloring powers of planar graphs. SIAM J Discret Math 16: pp. 651-662 CrossRef
  2. Albertson MO, Berman DM (1976) The acyclic chromatic number. In Proceedings of Seventh Southeastern Conference on Combinatorics. Graph Theory and Computing, Utilitas Mathematicsa Inc., Winniper, pp 51鈥?0
  3. Alon, N, McDiarmid, C, Reed, B (1991) Acyclic coloring of graphs. Random Struct Algorithms 2: pp. 277-288 CrossRef
  4. Bondy, JA, Murty, USR (1976) Graph theory with applications. Macmillan Press[M], New York
  5. Borodin, OV (1979) On acyclic colorings of planar graphs. Discret Math 25: pp. 211-236 CrossRef
  6. Borodin, OV, Woodall, DR (1995) Thirteen coloring numbers of outerplane graphs. Bull Inst Combin Appl 14: pp. 87-100
  7. Burnstein, MI (1979) Every 4-valent graph has an acyclic $$5$$ 5 -coloring. Soobsc Akad Nauk Grucin 93: pp. 21-24
  8. Cai, J, Wang, G, Yan, G (2013) The generalized acyclic chromatic number of graphs with large girth. Acta Math Sinica 56: pp. 27-30
  9. Dieng Y, Hocquard H, Naserasr R (2010) Acyclic colorings of graph with maximum degree. LaBRI, Manuscript
  10. Duffin, J (1965) Topology of series-parallel networks. J Math Anal Appl 10: pp. 303-318 CrossRef
  11. Fertin G, Raspaud A (2005) Acyclic colorings of graphs of maximum degree \(\Delta \) , European conference on combinatorics graph theory and applications, pp 389鈥?96
  12. Fertin, G, Raspaud, A (2008) Acyclic colorings of graphs of maximum degree five: nine colors are enough. Inf Process Lett 105: pp. 65-72 CrossRef
  13. Greenhill, C, Pikhurko, O (2005) Bounds on the generalized acyclic chromatic number of bounded degree graphs. Graphs Combin 21: pp. 407-419 CrossRef
  14. Gr眉nbaum, B (1973) Acyclic colorings of planar graphs. Israel J Math 14: pp. 390-408 CrossRef
  15. Hocquard, H (2011) Graphs with maximum degree 6 are acyclically 11-colorabe. Inf Process Lett 111: pp. 748-753 CrossRef
  16. Kostochka, AV, Stocker, C (2011) Graphs with maximum degree 5 are acyclically 7-colorable. Ars Mathematica Contemporanea 4: pp. 153-164
  17. Skulrattanakulchai, S (2004) Acyclic coloring of subcubic graphs. Inf Process Lett 92: pp. 161-167 CrossRef
  18. Yadav K, Varagani S, Kothapalli K, Venkaiah VCh (2009) Acyclic vertex coloring of graphs of maximum degree \(\Delta \) . Proceedings of Indian Mathematical Society
  19. Zhang, X, Wang, G, Yu, Y, Li, J, Liu, G (2012) On r-acyclic edge colorings of planar graphs. Discret Appl Math 160: pp. 2048-2053 CrossRef
  
• 刊物类别：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 vertex coloring of a graph G is r-acyclic if it is a proper vertex coloring such that every cycle \(C\) receives at least \(\min \{|C|,r\}\) colors. The \(r\) -acyclic chromatic number \(a_{r}(G)\) of \(G\) is the least number of colors in an \(r\) -acyclic coloring of \(G\) . Let \(G\) be a planar graph. By Four Color Theorem, we know that \(a_{1}(G)=a_{2}(G)=\chi (G)\le 4\) , where \(\chi (G)\) is the chromatic number of \(G\) . Borodin proved that \(a_{3}(G)\le 5\) . However when \(r\ge 4\) , the \(r\) -acyclic chromatic number of a class of graphs may not be bounded by a constant number. For example, \(a_{4}(K_{2,n})=n+2=\Delta (K_{2,n})+2\) for \(n\ge 2\) , where \(K_{2,n}\) is a complete bipartite (planar) graph. In this paper, we give a sufficient condition for \(a_{r}(G)\le r\) when \(G\) is a planar graph. In precise, we show that if \(r\ge 4\) and \(G\) is a planar graph with \(g(G)\ge \frac{10r-4}{3}\) , then \(a_{r}(G)\le r\) . In addition, we discuss the \(4\) -acyclic colorings of some special planar graphs.