Acyclic chromatic indices of planar graphs with large girth

作者：Wang Weifan^*; Shu Qiaojun; Wang Kan; Wang Ping

来源：Discrete Applied Mathematics, 2011, 159(12): 1239-1253.

DOI：10.1016/j.dam.2011.03.017

• Acyclic edge coloring
• Acyclic chromatic index
• Planar graph
• Girth

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 k such that G has an acyclic edge coloring using k colors.
In this paper, we prove that every planar graph G with girth g(G) and maximum degree Delta has a'(G) = Delta if there exists a pair (k, m) is an element of {(3, 11), (4, 8), (5, 7), (8, 6)} such that G satisfies Delta >= k and g(G) >= m.

• 出版日期2011-7-28
• 单位浙江师范大学