Acyclic coloring of graphs

Noga Alon, Colin Mcdiarmid, Bruce Reed

Research output: Contribution to journalArticle

164 Scopus citations

Abstract

A vertex coloring of a graph G is called acyclic if no two adjacent vertices have the same color and there is no two‐colored cycle in G. The acyclic chromatic number of G, denoted by A(G), is the least number of colors in an acyclic coloring of G. We show that if G has maximum degree d, then A(G) = 0(d4/3) as d → ∞. This settles a problem of Erdös who conjectured, in 1976, that A(G) = o(d2) as d → ∞. We also show that there are graphs G with maximum degree d for which A(G) = Ω(d4/3/(log d)1/3); and that the edges of any graph with maximum degree d can be colored by 0(d) colors so that no two adjacent edges have the same color and there is no two‐colored cycle. All the proofs rely heavily on probabilistic arguments.

Original languageEnglish (US)
Pages (from-to)277-288
Number of pages12
JournalRandom Structures & Algorithms
Volume2
Issue number3
DOIs
StatePublished - 1991
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

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

  • Cite this