Acyclic edge coloring of planar graphs without 5-cycles

作者：Shu, Qiaojun; Wang, Weifan^*; Wang, Yiqiao

来源：Discrete Applied Mathematics, 2012, 160(7-8): 1211-1223.

DOI：10.1016/j.dam.2011.12.016

• Acyclic edge coloring
• Planar graph
• Girth
• Maximum degree

An acyclic edge coloring of a graph G is a proper edge coloring such that no bichromatic cycles are produced. The acyclic chromatic index a'(G) of G is the smallest integer k such that G has an acyclic edge coloring using k colors. Fiamcik (1978) [9] and later Alon et al. (2001) [2] conjectured that a'(G) <= Delta + 2 for any simple graph G with maximum degree Delta. In this paper, we confirm this conjecture for planar graphs without 5-cycles.

• 出版日期2012-5
• 单位中国科学院数学与系统科学研究院; 浙江师范大学