Locally dense independent sets in regular graphs of large girth

Göring, Frank; Harant, Jochen GND; Rautenbach, Dieter GND; Schiermeyer, Ingo GND

For an integer d 3 let (d) be the supremum over all with the property that for every > 0 there exists some g() such that every d-regular graph of order n and y girth at least g() has an independent set of cardinality at least ( − )n. Extending an approach proposed by Lauer and Wormald (Large independent sets in regular graphs of large girth, J. Comb. Theory, Ser. B 97 (2007), 999-1009) and improving results due to Shearer (A note on the independence number of triangle-free graphs, II, J. Comb. Theory, Ser. B 53 (1991), 300-307) and Lauer and Wormald, we present the best known lower bounds for (d) for all d 3.

Cite

Citation style:
Göring Dr. rer. nat., F., Harant Prof. Dr. rer. nat. habil., J., Rautenbach Prof. Dr. rer. nat. habil., D., Schiermeyer Prof. Dr., I., 2007. Locally dense independent sets in regular graphs of large girth. Preprint /  Technische Universität Ilmenau, Institut für Mathematik, Preprint /  Technische Universität Ilmenau, Institut für Mathematik 07–14.
Could not load citation form. Default citation form is displayed.

Rights

Use and reproduction:
All rights reserved

Export