The maximum independent set problem in subclasses of subcubic graphs

DOI10.1016/J.DISC.2015.01.041zbMath1315.05099OpenAlexW2018464975MaRDI QIDQ2346341

Christoph Brause, Ingo Schiermeyer, 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.2015.01.041

zbMATH Keywords

independence numbermaximum independent setsubcubic graphaugmenting graphgraph reduction

Mathematics Subject Classification ID

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

Related Items (6)

Weighted independent sets in a subclass of \(P_6\)-free graphs ⋮ Computational complexity of the vertex cover problem in the class of planar triangulations ⋮ Algorithm to find a maximum 2-packing set in a cactus ⋮ Maximum independent sets near the upper bound ⋮ An efficient local search framework for the minimum weighted vertex cover problem ⋮ Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs
• Stability preserving transformations of 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é
• Some simplified NP-complete graph problems
• Struction revisited
• On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
• On the Maximum Independent Set Problem in Subclasses of Subcubic Graphs
• Stability in circular arc graphs
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• Reducibility among Combinatorial Problems

This page was built for publication: The maximum independent set problem in subclasses of subcubic graphs