Stable sets in \(k\)-colorable \(P_{5}\)-free graphs

DOI10.1016/j.ipl.2009.09.006zbMath1197.05148OpenAlexW1993788757MaRDI QIDQ990082

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

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

Related Items (3)

Combining decomposition approaches for the maximum weight stable set problem ⋮ Independent domination in finitely defined classes of graphs: polynomial algorithms ⋮ Domination, coloring and stability in \(P_5\)-reducible graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximum independent sets in subclasses of \(P_{5}\)-free graphs
• Computing independent sets in graphs with large girth
• Coloring the hypergraph of maximal cliques of a graph with no long path
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• On the stable set problem in special \(P_{5}\)-free graphs
• Threshold graphs and related topics
• A Note on k-Colorability of P 5-Free Graphs

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