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

DOI10.1007/S40306-020-00368-0MaRDI QIDQ778157zbMATH OpenOpenAlexFDO

Authors 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

maximum independent setstable 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)

Recommendations

• Maximum independent sets in graphs of low degree
• scientific article; zbMATH DE number 1003268
• scientific article; zbMATH DE number 1305487
• A simple and fast algorithm for Maximum Independent Set in 3-degree graphs (extended abstract)
• Exact Algorithms for Maximum Independent Set

Cites work

• scientific article; zbMATH DE number 3438749 (Why is no real title available?)
• A note on \(\alpha\)-redundant vertices in graphs
• Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs
• Local transformations of graphs preserving independence number
• Lower bounds on the independence number in terms of the degrees
• Maximum independent sets in graphs of low degree
• New sufficient conditions for \(\alpha\)-redundant vertices
• On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
• On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
• On the maximum independent set problem in subclasses of planar graphs
• On the maximum independent set problem in subclasses of subcubic graphs
• Reducibility among combinatorial problems
• The maximum independent set problem in subclasses of \(S_{i, j, k}\)-free graphs

Cited in

(14)

• A simple proof that finding a maximal independent set in a graph is in NC
• Computing maximum independent set on outerstring graphs and their relatives
• An optimal maximal independent set algorithm for bounded-independence graphs
• An Exact Algorithm for Maximum Independent Set in Degree-5 Graphs
• New properties of maximum independent set problem solution truncation rules or redundant branches
• Maximum independent sets in graphs of low degree
• Constructing concrete hard instances of the maximum independent set problem
• Further Improvement on Maximum Independent Set in Degree-4 Graphs
• An exact algorithm for maximum independent set in degree-5 graphs
• A sufficient condition to extend polynomial results for the maximum independent set problem
• The maximum independent set problem in subclasses of subcubic graphs
• The max quasi-independent set Problem
• scientific article; zbMATH DE number 5842466 (Why is no real title available?)
• On the Maximum Independent Set Problem in Subclasses of Subcubic Graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q778157)