Graphs with maximum degree 5 are acyclically 7-colorable

Alexandr V. Kostochka, Christopher J. Stocker

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.

Keywords


Acyclic coloring, maximum degree

Full Text:

PDF ABSTRACTS (EN/SI)


DOI: https://doi.org/10.26493/1855-3974.198.541

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications