Independent Sets near the Lower Bound in Bounded Degree Graphs

Date
2017-01-01
Authors
Dvořák, Zdeněk
Lidický, Bernard
Lidicky, Bernard
Journal Title
Journal ISSN
Volume Title
Publisher
Source URI
Altmetrics
Authors
Research Projects
Organizational Units
Mathematics
Organizational Unit
Journal Issue
Series
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).

Description
<p>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.</p>
Keywords
s independent set, bounded degree, ∆-colorable, fixed parameter tractability
Citation