Acyclic chromatic index of triangle-free 1-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)$. A graph is {\em $1$-planar} if it can be drawn on the plane such that every edge is crossed by at most one other edge. In this paper, we prove that every triangle-free $1$-planar graph $G$ has an acyclic edge coloring with $\Delta (G)+16$ colors.

7 pages. Lemma 6 was strengthened and the main result was slightly improved

References in corpus (4)

• Acyclic edge-coloring using entropy compression
• Further result on acyclic chromatic index of planar graphs
• Acyclic edge coloring of graphs
• An improved bound on acyclic chromatic index of planar graphs