Algorithmic aspects of acyclic edge colorings

N. Alon, A. Zaks

Research output: Contribution to journalArticlepeer-review

41 Scopus citations


A proper coloring of the edges of a graph G is called acyclic if there is no two-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) ≤ Δ A + 2 for almost all Delta;-regular graphs, including all A-regular graphs whose girth is at least cΔ log A. We prove that determining the acyclic edge chromatic number of an arbitrary graph is an NP-complete problem. For graphs G with sufficiently large girth in terms of Δ(G), we present deterministic polynomial-time algorithms that color the edges of G acyclically using at most Δ(G) + 2 colors.

Original languageEnglish (US)
Pages (from-to)611-614
Number of pages4
JournalAlgorithmica (New York)
Issue number4
StatePublished - 2002
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Computer Science Applications
  • Applied Mathematics


  • Acyclic edge coloring
  • Girth


Dive into the research topics of 'Algorithmic aspects of acyclic edge colorings'. Together they form a unique fingerprint.

Cite this