The independence number in graphs of maximum degree three

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

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 1/7 (4n − m − \lambda − tr) where \lambda 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 (A New Proof of the Independence Ratio of Triangle-Free Cubic Graphs, Discrete Math. 233 (2001), 233-237).

Zitieren

Zitierform:

Harant, Jochen / Henning, Michael A. / Rautenbach, Dieter / et al: The independence number in graphs of maximum degree three. 2007.

Zugriffsstatistik

Gesamt:
Volltextzugriffe:
Metadatenansicht:
12 Monate:
Volltextzugriffe:
Metadatenansicht:

Grafik öffnen

Rechte

Nutzung und Vervielfältigung:
Alle Rechte vorbehalten

Export