Document Open Access Logo

Independent Sets near the Lower Bound in Bounded Degree Graphs

Authors Zdenek Dvorák, Bernard Lidický

PDF
Thumbnail PDF

File

LIPIcs.STACS.2017.28.pdf
  • Filesize: 476 kB
  • 13 pages

Document Identifiers

Author Details

Zdenek Dvorák
Bernard Lidický

Cite AsGet BibTex

Zdenek Dvorák and Bernard Lidický. Independent Sets near the Lower Bound in Bounded Degree Graphs. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 28:1-28:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.STACS.2017.28

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 independent set of size at least n/Delta+k has a kernel of size O(k).
Keywords
  • independent set
  • bounded degree
  • Delta-colorable
  • fixed parameter tractability

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. M. Albertson, B. Bollobás, and S. Tucker. The independence ratio and the maximum degree of a graph. Congr. Numer., 17:43-50, 1976. Google Scholar
  2. K. Appel and W. Haken. Every planar map is four colorable, Part I: discharging. Illinois J. of Math., 21:429-490, 1977. Google Scholar
  3. K. Appel, W. Haken, and J. Koch. Every planar map is four colorable, Part II: reducibility. Illinois J. of Math., 21:491-567, 1977. Google Scholar
  4. Hans L. Bodlaender, Erik Demaine, Michael R. Fellows, Jiong Guo, Danny Hermelin, Daniel Lokshtanov, Moritz Müller, Venkatesh Raman, Johan van Rooij, and Frances A. Rosamond. Open problems in parameterized and exact computation. Technical Report UU-CS-2008-017, Utrecht University, 2008. Google Scholar
  5. Oleg V. Borodin. Criterion of chromaticity of a degree prescription. In IV All-Union Conf. on Theoretical Cybernetics (Novosibirsk), pages 127-128, 1977. Google Scholar
  6. Rowland Leonard Brooks. On colouring the nodes of a network. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 37, pages 194-197. Cambridge Univ Press, 1941. Google Scholar
  7. Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms, volume 4. Springer, 2015. Google Scholar
  8. Rodney G. Downey and Michael Ralph Fellows. Parameterized complexity. Springer Science &Business Media, 2012. Google Scholar
  9. Zdeněk Dvořák and Matthias Mnich. Large independent sets in triangle-free planar graphs. In Algorithms-ESA 2014, pages 346-357. Springer, 2014. Google Scholar
  10. Zdeněk Dvořák and Matthias Mnich. Large independent sets in triangle-free planar graphs. arXiv e-prints, 1311.2749v2, 2014. Google Scholar
  11. Zdenek Dvořák, Jean-Sébastien Sereni, and Jan Volec. Subcubic triangle-free graphs have fractional chromatic number at most 14/5. Journal of the London Mathematical Society, 89:641-662, 2014. Google Scholar
  12. Katherine Edwards and Andrew D. King. Bounding the fractional chromatic number of K_Δ-free graphs. SIAM J. Discrete Math., 27(2):1184-1208, 2013. Google Scholar
  13. P. Erdős, A. L. Rubin, and H. Taylor. Choosability in graphs. Congr. Numer., 26:125-157, 1980. Google Scholar
  14. Simeon Fajtlowicz. On the size of independent sets in graphs. Congr. Numer, 21:269-274, 1978. Google Scholar
  15. Michael R. Fellows, Jiong Guo, Dániel Marx, and Saket Saurabh. Data Reduction and Problem Kernels (Dagstuhl Seminar 12241). Dagstuhl Reports, 2(6):26-50, 2012. Google Scholar
  16. C. Heckman and R. Thomas. A new proof of the independence ratio of triangle-free cubic graphs. Discrete Math., 233:233-237, 2001. Google Scholar
  17. Iyad Kanj and Fenghui Zhang. On the independence number of graphs with maximum degree 3. Theoretical Computer Science, 478:51-75, 2013. Google Scholar
  18. Andrew D. King, Linyuan Lu, and Xing Peng. A fractional analogue of Brooks' theorem. SIAM Journal on Discrete Mathematics, 26(2):452-471, 2012. Google Scholar
  19. Matthias Mnich. Large independent sets in subquartic planar graphs. In WALCOM: Algorithms and Computation, pages 209-221. Springer, 2016. Google Scholar
  20. Rolf Niedermeier. Invitation to fixed-parameter algorithms, volume 31 of Oxford Lecture Series in Mathematics and its Applications. Oxford University Press, Oxford, 2006. Google Scholar
  21. N. Robertson, P. D. Seymour, and R. Thomas. Quickly excluding a planar graph. J. Combin. Theory, Ser. B, 62(2):323-348, 1994. Google Scholar
  22. W. Staton. Some Ramsey-type numbers and the independence ratio. Trans. Amer. Math. Soc., 256:353-370, 1979. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact