34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Journal or Book Title
Leibniz International Proceedings in Informatics
March 8-11, 2017
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
This work is licensed under a Creative Commons Attribution 3.0 License.
Dvořák, Zdeněk and Lidický, Bernard, "Independent Sets near the Lower Bound in Bounded Degree Graphs" (2017). Mathematics Conference Papers, Posters and Presentations. 5.