Choosability of P 5-Free Graphs

DOI10.1007/978-3-642-03816-7_33MaRDI QIDQ3182940zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Choosability on \(H\)-free graphs
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• A Note on k-Colorability of P 5-Free Graphs
• Three complexity results on coloring \(P _{k }\)-free graphs
• Three complexity results on coloring \(P_k\)-free graphs

Cites work

• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• A Linear Recognition Algorithm for Cographs
• A New Characterization of P 6-Free Graphs
• A Note on k-Colorability of P 5-Free Graphs
• Dominating cliques in \(P_ 5\)-free graphs
• Every planar graph is 5-choosable
• Graph Classes: A Survey
• Graph colorings with local constraints -- a survey
• scientific article; zbMATH DE number 446487 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2044943 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Some results on (a:b)-choosability
• The complexity of coloring graphs without long induced paths

Cited in

(10)

• On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs
• Independent feedback vertex set for P₅-free graphs
• Choosability on \(H\)-free graphs
• 2-connected chordal graphs and line graphs are \((1,5)\)-choosable
• List coloring in the absence of two subgraphs
• Double-exponential and triple-exponential bounds for choosability problems parameterized by treewidth
• Independent Feedback Vertex Set for P₅-free Graphs
• Connected vertex cover for \((sP_1+P_5)\)-free graphs
• Exact and parameterized algorithms for choosability
• On low tree-depth decompositions

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

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