d ‐Regular graphs of acyclic chromatic index at least d +2

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a ′( G ). It was conjectured by Alon, Sudakov and Zaks (and earlier by Fiamcik) that a ′( G )⩽Δ+2, where Δ=Δ( G ) denotes the maximum degree of the graph. Alon et al. also raised the question whether the complete graphs of even order are the only regular graphs which require Δ+2 colors to be acyclically edge colored. In this article, using a simple counting argument we observe not only that this is not true, but in fact all d ‐regular graphs with 2 n vertices and d > n , requires at least d + 2 colors. We also show that a ′( K n, n )⩾ n + 2, when n is odd using a more non‐trivial argument. (Here K n, n denotes the complete bipartite graph with n vertices on each side.) This lower bound for K n, n can be shown to be tight for some families of complete bipartite graphs and for small values of n . We also infer that for every d, n such that d ⩾5, n ⩾2 d + 3 and dn even, there exist d ‐regular graphs which require at least d +2‐colors to be acyclically edge colored. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 226–230, 2010