On the maximum independent set problem in graphs of bounded maximum degree

DOI10.1007/s40306-020-00368-0zbMath1442.05164OpenAlexW3036520051MaRDI QIDQ778157

D. Kharzeev

Publication date: 1 July 2020

Published in: Acta Mathematica Vietnamica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s40306-020-00368-0

zbMATH Keywords

stable setmaximum independent setlow degree graph

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• The maximum independent set problem in subclasses of \(S_{i, j, k}\)-free graphs
• Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs
• Lower bounds on the independence number in terms of the degrees
• On the maximum independent set problem in subclasses of subcubic graphs
• New sufficient conditions for \(\alpha\)-redundant vertices
• On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
• On the Maximum Independent Set Problem in Subclasses of Planar Graphs
• Local transformations of graphs preserving independence number
• On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
• Reducibility among Combinatorial Problems
• A note on \(\alpha\)-redundant vertices in graphs

This page was built for publication: On the maximum independent set problem in graphs of bounded maximum degree