Locally Dense Independent Sets in Regular Graphs of Large Girth—An Example of a New Approach

Frank Göring (), Jochen Harant (), Dieter Rautenbach () and Ingo Schiermeyer ()
Additional contact information
Frank Göring: TU Chemnitz, Fakultät für Mathematik
Jochen Harant: TU Ilmenau, Institut für Mathematik
Dieter Rautenbach: TU Ilmenau, Institut für Mathematik
Ingo Schiermeyer: Technische Universität Bergakademie Freiberg, Institut für Diskrete Mathematik und Algebra

Chapter 8 in Research Trends in Combinatorial Optimization, 2009, pp 163-183 from Springer

Abstract: Summary We present an example for a new approach which seems applicable to every graph theoretical concept defined by local conditions and regular graphs of large girth. It combines a random outer procedure processing the graph in rounds with a virtually arbitrary algorithm solving local instances within each round and combines the local solutions to a global one. The local uniformity of the considered instances and the randomness of the outer procedure make the asymptotic analysis possible. Here we apply this approach to the simplest yet fundamental example of a locally defined graph theoretical concept: independent sets in graphs. 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 girth at least g(ε) has an independent set of cardinality at least (α−ε)n. Considerably extending the work of Lauer and Wormald (Large independent sets in regular graphs of large girth, J. Comb. Theory, Ser. B 97, 999–1009, 2007) and improving results due to Shearer (A note on the independence number of triangle-free graphs, II, J. Comb. Theory, Ser. B 53, 300–307, 1991) and Lauer and Wormald, we present the best known lower bounds for α(d) for all d≥3.

Date: 2009
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-540-76796-1_8

Ordering information: This item can be ordered from
http://www.springer.com/9783540767961

DOI: 10.1007/978-3-540-76796-1_8

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().