Graphs with maximum degree 5 are acyclically 7-colorable

Alexandr V. Kostochka, Christopher Stocker

Research output: Contribution to journalArticlepeer-review

Abstract

An acyclic coloring is a proper coloring with the additional property that the union of any two color classes induces a forest. We show that every graph with maximum degree at most 5 has an acyclic 7-coloring. We also show that every graph with maximum degree at most r has an acyclic (1 + ⌊(r+1) 2/4 ⌋)-coloring.

Original languageEnglish (US)
Pages (from-to)153-164
Number of pages12
JournalArs Mathematica Contemporanea
Volume4
Issue number1
DOIs
StatePublished - 2011

Keywords

  • Acyclic coloring
  • Maximum degree

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Algebra and Number Theory
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Graphs with maximum degree 5 are acyclically 7-colorable'. Together they form a unique fingerprint.

Cite this