Premium
d ‐Regular graphs of acyclic chromatic index at least d +2
Author(s) -
Basavaraju Manu,
Chandran L. Sunil,
Kummini Manoj
Publication year - 2010
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20422
Subject(s) - combinatorics , mathematics , edge coloring , bipartite graph , brooks' theorem , discrete mathematics , list coloring , graph , upper and lower bounds , 1 planar graph , chordal graph , graph power , line graph , mathematical analysis
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