Every planar graph has an acyclic 8-coloring

DOI10.1215/S0012-7094-74-04119-2zbMath0284.05103MaRDI QIDQ1844681

John Mitchem

Publication date: 1974

Published in: Duke Mathematical Journal (Search for Journal in Brave)

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Related Items (41)

Construction of acyclically 4-colourable planar triangulations with minimum degree 4 ⋮ A sufficient condition for planar graphs to be acyclically 5-choosable ⋮ Good and semi-strong colorings of oriented planar graphs ⋮ On acyclic colorings of graphs on surfaces ⋮ Acyclic coloring with few division vertices ⋮ Acyclic 4-choosability of planar graphs ⋮ Acyclic colorings of graph subdivisions revisited ⋮ An improved upper bound for the acyclic chromatic number of 1-planar graphs ⋮ Injective edge-coloring of subcubic graphs ⋮ Improved bounds on linear coloring of plane graphs ⋮ Graphs with maximum degree \(6\) are acyclically \(11\)-colorable ⋮ Acyclic 4-choosability of planar graphs without intersecting short cycles ⋮ Planar graphs without 4- and 5-cycles are acyclically 4-choosable ⋮ Acyclic vertex coloring of graphs of maximum degree six ⋮ Acyclic 6-choosability of planar graphs without adjacent short cycles ⋮ Acyclic 4-choosability of planar graphs without 4-cycles ⋮ Acyclic 5-choosability of planar graphs without 4-cycles ⋮ Acyclic and star coloring of \(P_4\)-reducible and \(P_4\)-sparse graphs ⋮ Acyclic 5-choosability of planar graphs without 4-cycles ⋮ Acyclic 4‐Choosability of Planar Graphs with No 4‐ and 5‐Cycles ⋮ Acyclically 3-colorable planar graphs ⋮ Acyclic colorings of locally planar graphs ⋮ Note to the paper of Grünbaum on acyclic colorings ⋮ Acyclic 4-choosability of planar graphs with neither 4-cycles nor triangular 6-cycles ⋮ Acyclic 4-choosability of planar graphs without adjacent short cycles ⋮ On acyclic 4-choosability of planar graphs without short cycles ⋮ On acyclic colorings of planar graphs. (Reprint) ⋮ Circular vertex arboricity ⋮ Acyclic chromatic indices of planar graphs with large girth ⋮ An acyclic analogue to Heawood's theorem ⋮ Acyclic \(L\)-coloring of graphs with maximum degrees 5 and 6 ⋮ On acyclic 4-choosability of planar graphs without cycles of length 4, 7 and 9 ⋮ Every planar graph has an acyclic 7-coloring ⋮ Acyclic 3-coloring of generalized Petersen graphs ⋮ On acyclic colorings of planar graphs ⋮ Planar graphs without 4-cycles are acyclically 6-choosable ⋮ Linear coloring of planar graphs with large girth ⋮ Acyclic 5-choosability of planar graphs with neither 4-cycles nor chordal 6-cycles ⋮ Acyclic coloring of IC-planar graphs ⋮ Planar graphs without 4, 5 and 8-cycles are acyclically 4-choosable ⋮ A Conjecture of Borodin and a Coloring of Grünbaum

This page was built for publication: Every planar graph has an acyclic 8-coloring