New sufficient conditions for \(\alpha\)-redundant vertices

DOI10.1016/j.disc.2014.07.002zbMath1315.05101OpenAlexW2023377256MaRDI QIDQ2346329

Ingo Schiermeyer, Christoph Brause, Ngoc C. Lê

Publication date: 1 June 2015

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

Full work available at URL: https://doi.org/10.1016/j.disc.2014.07.002

zbMATH Keywords

stable setindependence numberstability numbermaximum independent setgraph transformationgraph reduction\(\alpha\)-redundant

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (9)

Combinatorics and algorithms for augmenting graphs ⋮ The maximum independent set problem in subclasses of \(S_{i, j, k}\)-free graphs ⋮ Independent sets in some classes of \(S_{i,j,k}\)-free graphs ⋮ Weighted independent sets in a subclass of \(P_6\)-free graphs ⋮ On sequential heuristic methods for the maximum independent set problem ⋮ Independent Sets in Classes Related to Chair-Free Graphs ⋮ Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs ⋮ On the maximum independent set problem in graphs of bounded maximum degree ⋮ Extending the MAX algorithm for maximum independent set

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polynomial algorithms for the maximum stable set problem on particular classes of \(P_{5}\)-free graphs
• Stability preserving transformations of graphs
• On finding augmenting graphs
• Some results on graphs without long induced paths
• On maximal independent sets of vertices in claw-free graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Complement reducible graphs
• Lower bounds on the stability number of graphs computed in terms of degrees
• On the stability number of claw-free \(P_5\)-free and more general graphs
• Robust algorithms for the stable set problem
• On \(\alpha\)-redundant vertices in \(P_{5}\)-free graphs
• Stability number in subclasses of \(P_5\)-free graphs
• Lower bounds on the independence number in terms of the degrees
• On the stable set problem in special \(P_{5}\)-free graphs
• On the Maximum Independent Set Problem in Subclasses of Subcubic Graphs
• On the Maximum Independent Set Problem in Subclasses of Planar Graphs
• A Linear Recognition Algorithm for Cographs
• Stability in circular arc graphs
• Réductions et conditions d'optimalité dans le problème de l'ensemble stable de poids maximal
• Algorithmic Aspects of Vertex Elimination on Graphs
• Stable sets for (P_{6}, K_{2,3})-free graphs
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• Independent Set in P₅-Free Graphs in Polynomial Time
• A note on \(\alpha\)-redundant vertices in graphs

This page was built for publication: New sufficient conditions for \(\alpha\)-redundant vertices