Choosability of P 5-Free Graphs

DOI10.1007/978-3-642-03816-7_33zbMath1250.68127OpenAlexW1890319011MaRDI QIDQ3182940

Petr A. Golovach, Pinar Heggernes

Publication date: 16 October 2009

Published in: Mathematical Foundations of Computer Science 2009 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-03816-7_33

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15)

Related Items (6)

List coloring in the absence of two subgraphs ⋮ On low tree-depth decompositions ⋮ On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs ⋮ Independent feedback vertex set for \(P_5\)-free graphs ⋮ Connected vertex cover for \((sP_1+P_5)\)-free graphs ⋮ Independent Feedback Vertex Set for P_5-free Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some results on \((a:b)\)-choosability
• Dominating cliques in \(P_ 5\)-free graphs
• Every planar graph is 5-choosable
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• A New Characterization of P 6-Free Graphs
• A Note on k-Colorability of P 5-Free Graphs
• A Linear Recognition Algorithm for Cographs
• Graph colorings with local constraints -- a survey
• Graph Classes: A Survey

This page was built for publication: Choosability of P 5-Free Graphs