2001/06/07 by Noga Alon, Benny Sudakov, Ayal Zaks · 2 citations
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Combinatorics #Mathematics #Edge coloring #Conjecture #Discrete mathematics #Graph #Triangle-free graph #Upper and lower bounds #Graph power #1-planar graph #Chordal graph #Line graph
paper · doi:10.1002/jgt.1010
openalex publication_date 2001/06/07 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/22
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