Upper Bounds on the Acyclic Chromatic Index of Degenerate Graphs
share
An acyclic edge coloring of a graph is a proper edge coloring without any bichromatic cycles. The acyclic chromatic index of a graph G denoted by a'(G), is the minimum k such that G has an acyclic edge coloring with k colors. Fiamčík conjectured that a'(G) ≤Δ+2 for any graph G with maximum degree Δ. A graph G is said to be k-degenerate if every subgraph of G has a vertex of degree at most k. Basavaraju and Chandran proved that the conjecture is true for 2-degenerate graphs. We prove that for a 3-degenerate graph G, a'(G) ≤Δ+5, thereby bringing the upper bound closer to the conjectured bound. We also consider k-degenerate graphs with k ≥ 4 and give an upper bound for the acyclic chromatic index of the same.
READ FULL TEXT