Acyclic coloring of graphs of maximum degree five: nine colors are enough

DOI10.1016/j.ipl.2007.08.022zbMath1183.05027WikidataQ56390803 ScholiaQ56390803MaRDI QIDQ2380043

Guillaume Fertin, Andre Raspaud

Publication date: 24 March 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2007.08.022

zbMATH Keywords

acyclic chromatic number; graph algorithms; acyclic coloring algorithm; maximum degree 5

Mathematics Subject Classification ID

05C15: Coloring of graphs and hypergraphs

Related Items

Unnamed Item, A polyhedral study of the acyclic coloring problem, Acyclically 4-colorable triangulations, Acyclic total colorings of planar graphs without \(l\) cycles, Acyclic vertex coloring of graphs of maximum degree 5, Acyclic and star colorings of cographs, Acyclic and star coloring of \(P_4\)-reducible and \(P_4\)-sparse graphs, Graphs with maximum degree \(6\) are acyclically \(11\)-colorable, Acyclic choosability of graphs with bounded degree, Acyclic coloring of claw-free graphs with small degree, Acyclic \(L\)-coloring of graphs with maximum degrees 5 and 6, Acyclic coloring of graphs and entropy compression method, Acyclic coloring of graphs with maximum degree at most six, The \(r\)-acyclic chromatic number of planar graphs, Acyclic vertex coloring of graphs of maximum degree six, Acyclic coloring of graphs with maximum degree 7, On b-acyclic chromatic number of a graph, Exploring the disjunctive rank of some facet-inducing inequalities of the acyclic coloring polytope

Cites Work

• Unnamed Item
• Acyclic colorings of subcubic graphs
• Acyclic colorings of products of trees
• Acyclic and \(k\)-distance coloring of the grid
• On acyclic colorings of planar graphs
• Acyclic Colourings of Planar Graphs with Large Girth
• Acyclic coloring of graphs
• The chromatic number of oriented graphs
• Acyclic colorings of planar graphs
• Acyclic colouring of 1-planar graphs