Acyclic chromatic index of chordless graphs

Abstract

An acyclic edge coloring of a graph is a proper edge coloring with no bichromatic cycles. The acyclic chromatic index of a graph G denoted by a′(G), is the minimum integer k such that G has an acyclic edge coloring with k colors. It was conjectured by Fiamčík [13] that a′(G)≤Δ+2 for any graph G with maximum degree Δ. Linear arboricity of a graph G, denoted by la(G), is the minimum number of linear forests into which the edges of G can be partitioned. A graph is said to be chordless if no cycle in the graph contains a chord. By a result of Basavaraju and Chandran [6], if G is chordless, then a′(G)≤Δ+1. Machado, de Figueiredo and Trotignon [23] proved that the chromatic index of a chordless graph is Δ when Δ≥3. We prove that for any chordless graph G, a′(G)=Δ, when Δ≥3. Notice that this is an improvement over the result of Machado et al., since any acyclic edge coloring is also a proper edge coloring and we are using the same number of colors. As a byproduct, we prove that [Formula presented], when Δ≥3. To obtain the result on acyclic chromatic index, we prove a structural result on chordless graphs which is a refinement of the structure given by Machado et al. [23] in case of chromatic index. This might be of independent interest. © 2023 Elsevier B.V.