On coloring graphs without induced forests

DOI10.1007/978-3-642-17514-5_14MaRDI QIDQ3060770zbMATH OpenOpenAlexFDO

Authors Petr A. Golovach, Daniël Paulusma, Jian Song, Hajo Broersma

Publication date 9 December 2010

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-17514-5_14

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Coloring graphs with forbidden induced subgraphs
• Determining the chromatic number of triangle-free 2P₃-free graphs in polynomial time
• Updating the complexity status of coloring graphs without a fixed induced linear forest

Cited in

(10)

• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• On vertex coloring without monochromatic triangles
• Narrowing Down the Gap on the Complexity of Coloring P k -Free Graphs
• Colouring vertices of triangle-free graphs
• Determining the chromatic number of triangle-free 2P₃-free graphs in polynomial time
• On the parameterized complexity of coloring graphs in the absence of a linear forest
• 2P₃-free graphs that do not contain any induced subdivision of K₄ are 4-colorable
• Precoloring extension with demands on paths
• Updating the complexity status of coloring graphs without a fixed induced linear forest
• Colouring vertices of triangle-free graphs without forests

This page was built for publication: On coloring graphs without induced forests

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3060770)