Further result on acyclic chromatic index of planar graphs

Abstract

An acyclic edge coloring of a graph $G$ is a proper edge coloring such that every cycle is colored with at least three colors. The acyclic chromatic index $\chiup_{a}'(G)$ of a graph $G$ is the least number of colors in an acyclic edge coloring of $G$. It was conjectured that $\chiup'_{a}(G)\leq Δ(G) + 2$ for any simple graph $G$ with maximum degree $\Delta (G)$. In this paper, we prove that every planar graph $G$ admits an acyclic edge coloring with $\Delta (G)+6$ colors.

23 pages, 20 figures, mainly revised Lemma 8 in Discrete Applied Mathematics, 2015. arXiv admin note: text overlap with arXiv:1302.2405

References in corpus (2)

• Acyclic edge-coloring using entropy compression
• Acyclic edge coloring of graphs

Cited by in corpus (3)

• Acyclic chromatic index of triangle-free 1-planar graphs
• The Acyclic Chromatic Index is Less than the Double of the Max Degree
• Acyclic edge coloring conjecture is true on planar graphs without intersecting triangles