Premium
Acyclic edge coloring of graphs with maximum degree 4
Author(s) -
Basavaraju Manu,
Chandran L. Sunil
Publication year - 2009
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.20376
Subject(s) - combinatorics , edge coloring , mathematics , list coloring , complete coloring , brooks' theorem , graph power , graph coloring , conjecture , fractional coloring , discrete mathematics , simple graph , graph , line graph
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 that for any simple and finite graph G , a ′( G )⩽Δ + 2, where Δ=Δ( G ) denotes the maximum degree of G . We prove the conjecture for connected graphs with Δ( G )⩽4, with the additional restriction that m ⩽2 n −1, where n is the number of vertices and m is the number of edges in G . Note that for any graph G , m ⩽2 n , when Δ( G )⩽4. It follows that for any graph G if Δ( G )⩽4, then a ′( G )⩽7. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 192–209, 2009