The maximum independent set problem in subclasses of \(S_{i, j, k}\)-free graphs

DOI10.1016/J.ENDM.2015.06.008zbMath1346.05218OpenAlexW2197961740MaRDI QIDQ322186

Christoph Brause, Ingo Schiermeyer, Ngoc C. Lê

Publication date: 14 October 2016

Full work available at URL: https://doi.org/10.1016/j.endm.2015.06.008

zbMATH Keywords

maximum independent setaugmenting graph\(\alpha\)-redundant vertex

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (4)

Augmenting approach for some maximum set problems ⋮ Independent sets in some classes of \(S_{i,j,k}\)-free graphs ⋮ Independent Sets in Classes Related to Chair-Free Graphs ⋮ On the maximum independent set problem in graphs of bounded maximum degree

Cites Work

• Unnamed Item
• On finding augmenting graphs
• Maximum independent sets in subclasses of \(P_{5}\)-free graphs
• Finding augmenting chains in extensions of claw-free graphs
• On maximal independent sets of vertices in claw-free graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• An augmenting graph approach to the stable set problem in \(P_{5}\)-free graphs
• \(P_{5}\)-free augmenting graphs and the maximum stable set problem
• New sufficient conditions for \(\alpha\)-redundant vertices
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• A note on \(\alpha\)-redundant vertices in graphs

This page was built for publication: The maximum independent set problem in subclasses of \(S_{i, j, k}\)-free graphs