Algorithmic aspects of acyclic edge colorings

N. Alon, A. Zaks

Research output: Contribution to journalArticle

35 Scopus citations

Abstract

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)
Volume32
Issue number4
DOIs
StatePublished - Jan 1 2002
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Keywords

  • Acyclic edge coloring
  • Girth

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

  • Cite this