2011/03/24 by Alexandr Kostochka, Christopher Stocker · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #Mathematics #Combinatorics #Degree (music) #Complete coloring #List coloring #Edge coloring #Greedy coloring #Graph #Fractional coloring #Discrete mathematics #Graph coloring #Property (philosophy) #Graph power #Line graph
paper · pdf · doi:10.26493/1855-3974.198.541
openalex publication_date 2011/03/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
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.