Independent sets near the lower bound in bounded degree graphs

DOI10.4230/LIPICS.STACS.2017.28MaRDI QIDQ4636626zbMATH OpenFDO

Authors Zdeněk Dvořák, Bernard Lidický

Publication date 19 April 2018

Full work available at URL https://arxiv.org/abs/1609.09134

zbMATH Keywords

independent setbounded degreefixed parameter tractability\(\Delta\)-colorable

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: By Brook's Theorem, every n-vertex graph of maximum degree at most Delta >= 3 and clique number at most Delta is Delta-colorable, and thus it has an independent set of size at least n/Delta. We give an approximate characterization of graphs with independence number close to this bound, and use it to show that the problem of deciding whether such a graph has an indepdendent set of size at least n/Delta+k has a kernel of size O(k).

Recommendations

• On the Independence Number of Graphs with Maximum Degree 3
• On the independence number of graphs with maximum degree 3
• Bounded-degree independent sets in planar graphs
• scientific article; zbMATH DE number 1979518
• scientific article; zbMATH DE number 1003268

Cited in

(8)

• Lower bounds for constant degree independent sets
• Turán’s Theorem Through Algorithmic Lens
• Complexes of graphs with bounded independence number
• On the independence number of graphs with maximum degree 3
• Maximum independent sets near the upper bound
• Lower bounds for the independence and \(k\)-independence number of graphs using the concept of degenerate degrees
• Bounded-degree independent sets in planar graphs
• The Benes Network is q*(q-1)/2n-Almost q-set-wise Independent

This page was built for publication: Independent sets near the lower bound in bounded degree graphs

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