On maximum independent sets in \(P_{5}\)-free graphs

DOI10.1016/j.dam.2010.01.007zbMath1210.05164OpenAlexW2048280336MaRDI QIDQ708334

Bert Randerath, Ingo Schiermeyer

Publication date: 11 October 2010

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2010.01.007

zbMATH Keywords

independence numberindependent setsubexponential algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (5)

A subexponential-time algorithm for the maximum independent set problem in \(P_t\)-free graphs ⋮ Maximum weight independent sets for (\(P_7\),triangle)-free graphs in polynomial time ⋮ Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs ⋮ Independent domination in finitely defined classes of graphs: polynomial algorithms ⋮ Spectral properties of cographs andP₅-free graphs

Cites Work

• Complete description of forbidden subgraphs in the structural domination problem
• Dominating cliques in \(P_ 5\)-free graphs
• Hereditary Domination in Graphs: Characterization with Forbidden Induced Subgraphs
• A New Characterization of P 6-Free Graphs
• Measure and conquer
• Unnamed Item

This page was built for publication: On maximum independent sets in \(P_{5}\)-free graphs