Acyclic (Δ + 2)-Edge Coloring of Toroidal Graphs Without Short Cycles

Abstract

An acyclic edge coloring of a graph G is a proper edge coloring such that G contains no bichromatic cycles. The acyclic chromatic index χa′(G) is the minimum number of colors required for an acyclic edge coloring. Fiamčik and Alon et al. independently conjectured that χa′(G)≤Δ+2 for every simple graph G with maximum degree Δ; this is known as the Acyclic Edge Coloring Conjecture (AECC). In this paper, we prove that the AECC holds for every C4-free toroidal graph and every C5-free and K4-free toroidal graph. As a key step in the proofs, we establish that every such 2-connected toroidal graph with a maximum degree of at least 5 contains one of four groups of local configurations.