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 language | English (US) |
---|---|
Pages (from-to) | 153-164 |
Number of pages | 12 |
Journal | Ars Mathematica Contemporanea |
Volume | 4 |
Issue number | 1 |
DOIs | |
State | Published - 2011 |
Keywords
- Acyclic coloring
- Maximum degree
ASJC Scopus subject areas
- Theoretical Computer Science
- Algebra and Number Theory
- Geometry and Topology
- Discrete Mathematics and Combinatorics