Acyclic edge coloring of planar graphs without 4-cycles

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

来源：Journal of Combinatorial Optimization, 2013, 25(4): 562-586.

DOI：10.1007/s10878-012-9474-y

• Acyclic edge coloring
• Planar graph
• Cycle
• 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. Fiamik (Math. Slovaca 28:139-145, 1978) and later Alon, Sudakov and Zaks (J. Graph Theory 37:157-167, 2001) conjectured that a'(G)a parts per thousand currency sign Delta+2 for any simple graph G with maximum degree Delta. In this paper, we confirm this conjecture for planar graphs G with Delta not equal 4 and without 4-cycles.

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