Premium
Acyclic edge colorings of graphs
Author(s) -
Alon Noga,
Sudakov Benny,
Zaks Ayal
Publication year - 2001
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.1010
Subject(s) - combinatorics , mathematics , edge coloring , conjecture , discrete mathematics , triangle free graph , graph , graph power , chordal graph , 1 planar graph , line graph
Abstract A proper coloring of the edges of a graph G is called acyclic if there is no 2‐colored cycle in G . The acyclic edge chromatic number of G , denoted by a′ ( G ), is the least number of colors in an acyclic edge coloring of G . For certain graphs G , a′ ( G ) ≥ Δ( G ) + 2 where Δ( G ) is the maximum degree in G . It is known that a′ ( G ) ≤ 16 Δ( G ) for any graph G . We prove that there exists a constant c such that a′ ( G ) ≤ Δ( G ) + 2 for any graph G whose girth is at least c Δ( G ) log Δ( G ), and conjecture that this upper bound for a′ ( G ) holds for all graphs G . We also show that a′ ( G ) ≤ Δ + 2 for almost all Δ‐regular graphs. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 157–167, 2001