The independence number in graphs of maximum degree three

Jochen Harant, Michael A. Henning, Dieter Rautenbach, Ingo Schiermeyer

Research output: Contribution to journalArticlepeer-review

18 Citations (Scopus)

Abstract

We prove that a K4-free graph G of order n, size m and maximum degree at most three has an independent set of cardinality at least frac(1, 7) (4 n - m - λ - t r), where λ counts the number of components of G whose blocks are each either isomorphic to one of four specific graphs or edges between two of these four specific graphs and tr is the maximum number of vertex-disjoint triangles in G. Our result generalizes a bound due to Heckman and Thomas [C.C. Heckman, R. Thomas, A new proof of the independence ratio of triangle-free cubic graphs, Discrete Math. 233 (2001) 233-237].

Original languageEnglish
Pages (from-to)5829-5833
Number of pages5
JournalDiscrete Mathematics
Volume308
Issue number23
DOIs
Publication statusPublished - 6 Dec 2008
Externally publishedYes

Keywords

  • Cubic graph
  • Independence
  • Triangle

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'The independence number in graphs of maximum degree three'. Together they form a unique fingerprint.

Cite this