Acyclic edge colorings of graphs

Noga Alon, Benny Sudakov, Ayal Zaks

Research output: Contribution to journalArticlepeer-review

114 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)157-167
Number of pages11
JournalJournal of Graph Theory
Volume37
Issue number3
DOIs
StatePublished - Jul 2001
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Keywords

  • Acyclic chromatic number
  • Acyclic edge coloring
  • Graph

Fingerprint

Dive into the research topics of 'Acyclic edge colorings of graphs'. Together they form a unique fingerprint.

Cite this