Acyclic colourings of planar graphs with large girth

O. V. Borodin, A. V. Kostochka, D. R. Woodall

Research output: Contribution to journalArticlepeer-review

Abstract

A proper vertex-colouring of a graph is acyclic if there are no 2-coloured cycles. It is known that every planar graph is acyclically 5-colourable, and that there are planar graphs with acyclic chromatic number χa = 5 and girth g = 4. It is proved here that a planar graph satisfies χa ≤ 4 if g ≥ 5 and χa ≤ 3 if g ≥ 7.

Original languageEnglish (US)
Pages (from-to)344-352
Number of pages9
JournalJournal of the London Mathematical Society
Volume60
Issue number2
DOIs
StatePublished - Oct 1999
Externally publishedYes

ASJC Scopus subject areas

  • General Mathematics

Fingerprint

Dive into the research topics of 'Acyclic colourings of planar graphs with large girth'. Together they form a unique fingerprint.

Cite this