Acyclic Chromatic Index of Chordless Graphs
share
An acyclic edge coloring of a graph is a proper edge coloring in which there are no bichromatic cycles. The acyclic chromatic index of a graph G denoted by a'(G), is the minimum positive integer k such that G has an acyclic edge coloring with k colors. It has been conjectured by Fiamčík 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. Every 2-connected chordless graph is a minimally 2-connected graph. It was shown by Basavaraju and Chandran that if G is 2-degenerate, then a'(G) ≤Δ+1. Since chordless graphs are also 2-degenerate, we have a'(G) ≤Δ+1 for any chordless graph G. Machado, de Figueiredo and Trotignon proved that the chromatic index of a chordless graph is Δ when Δ≥ 3. They also obtained a polynomial time algorithm to color a chordless graph optimally. We improve this result by proving that the acyclic chromatic index of a chordless graph is Δ, except when Δ=2 and the graph has a cycle, in which case it is Δ+1. We also provide the sketch of a polynomial time algorithm for an optimal acyclic edge coloring of a chordless graph. As a byproduct, we also prove that la(G) = ⌈Δ/2⌉, unless G has a cycle with Δ=2, in which case la(G) = ⌈Δ+1/2⌉ = 2. 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, de Figueiredo and Trotignon for this class of graphs. This might be of independent interest.
READ FULL TEXT