Campus Units

Mathematics

Document Type

Conference Proceeding

Conference

34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Publication Version

Published Version

Publication Date

2017

Journal or Book Title

Leibniz International Proceedings in Informatics

First Page

28

Conference Date

March 8-11, 2017

City

Hannover, Germany

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

Comments

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.

Creative Commons License

Creative Commons Attribution 3.0 License
This work is licensed under a Creative Commons Attribution 3.0 License.

Copyright Owner

The Authors

Language

en

File Format

application/pdf

Share

Article Location

 
COinS