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