Independent sets near the lower bound in bounded degree graphs

DOI10.4230/LIPICS.STACS.2017.28zbMATH Open1402.05164arXiv1609.09134MaRDI QIDQ4636626FDOQ4636626

Bernard Lidický, Zdeněk Dvořák

Publication date: 19 April 2018

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).

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)

Cited In (5)

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

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)