Stable sets in k-colorable P₅-free graphs

DOI10.1016/J.IPL.2009.09.006MaRDI QIDQ990082zbMATH OpenOpenAlexFDO

Authors Frédéric Maffray

Publication date 2 September 2010

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

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

zbMATH Keywords

stabilitygraph algorithm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Some results on maximum stable sets in certain \(P_{5}\)-free graphs
• On 3-colorable \(P_5\)-free graphs
• On the stable set problem in special \(P_{5}\)-free graphs
• Some results on stable sets for \(k\)-colorable \(P_{6}\)-free graphs and generalizations
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time

Cites work

• 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 4183452 (Why is no real title available?)
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• A Note on k-Colorability of P 5-Free Graphs
• Coloring the hypergraph of maximal cliques of a graph with no long path
• Computing independent sets in graphs with large girth
• Maximum independent sets in subclasses of \(P_{5}\)-free graphs
• On the stable set problem in special \(P_{5}\)-free graphs
• The complexity of coloring graphs without long induced paths
• Threshold graphs and related topics

Cited in

(15)

• An augmenting graph approach to the stable set problem in \(P_{5}\)-free graphs
• Combining decomposition approaches for the maximum weight stable set problem
• Some results on stable sets for \(k\)-colorable \(P_{6}\)-free graphs and generalizations
• Stability in \(P_5\)- and banner-free graphs
• Some results on maximum stable sets in certain \(P_{5}\)-free graphs
• On the stable set problem in special \(P_{5}\)-free graphs
• Penta-extensions of hereditary classes of graphs
• A one-to-one correspondence between colorings and stable sets
• Towards Erdős-Hajnal for graphs with no 5-hole
• Independent domination in finitely defined classes of graphs: polynomial algorithms
• Domination, coloring and stability in \(P_5\)-reducible graphs
• Stable set and clique polytopes of \((P_{5},\,\mathrm{gem})\)-free graphs
• A Note on k-Colorability of P 5-Free Graphs
• On 3-colorable \(P_5\)-free graphs
• Hitting all maximum stable sets in \(P_5\)-free graphs

This page was built for publication: Stable sets in \(k\)-colorable \(P_{5}\)-free graphs

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