Presentation
Independent Sets near the Lower Bound in Bounded Degree Graphs
Leibniz International Proceedings in Informatics
Document Type
Conference Proceeding
Disciplines
Conference
34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Publication Version
Published Version
Publication Date
1-1-2017
Conference Date
March 8-11, 2017
Geolocation
(52.3758916, 9.732010400000036)
Abstract
By Brook’s Theorem, every n-vertex graph of maximum degree at most ∆≥3 and clique number at most ∆ is ∆-colorable, and thus it has an independent set of size at least n/∆. 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 independent set of size at least n/∆ +k has a kernel of size O(k).
Creative Commons License
Creative Commons Attribution 3.0
Copyright Owner
The Authors
Copyright Date
2017
Language
en
File Format
application/pdf
Citation Information
Zdeněk Dvořák and Bernard Lidický. "Independent Sets near the Lower Bound in Bounded Degree Graphs" Hannover, GermanyLeibniz International Proceedings in Informatics (2017) p. 28 Available at: http://works.bepress.com/bernard-lidicky/33/
This article is published as Dvořák, Zdeněk and Bernard Lidický. "Independent Sets near the Lower Bound in Bounded Degree Graphs." Leibniz International Proceedings in Informatics, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). ed. Heribert Vollmer and Brigitte Vallée; Article No. 28; pp. 28:1–28:1. Posted with permission.