Large independent sets in regular graphs of large girth

DOI10.1016/j.jctb.2007.02.006zbMath1183.05058MaRDI QIDQ2384807

Joseph Lauer, Nicholas C. Wormald

Publication date: 10 October 2007

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jctb.2007.02.006

zbMATH Keywords

greedy algorithm; independent set; differential equation method; independence ratio; regular graphs of large girth

Mathematics Subject Classification ID

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Related Items

Factor of IID Percolation on Trees, Properties of regular graphs with large girth via local algorithms, New lower bounds on independence number in triangle-free graphs in terms of order, maximum degree and girth, Independent sets in graphs, Dynamic monopolies for degree proportional thresholds in connected graphs of girth at least five and trees, Lower bounds on the independence number of certain graphs of odd girth at least seven, Perfect matchings as IID factors on non-amenable groups, Interpolating between bounds on the independence number, Independence ratio and random eigenvectors in transitive graphs, Locally Dense Independent Sets in Regular Graphs of Large Girth—An Example of a New Approach, Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs, Invariant Gaussian processes and independent sets on regular graphs of large girth, Induced Forests in Regular Graphs with Large Girth, Randomized Greedy Algorithms for Independent Sets and Matchings in Regular Graphs: Exact Results and Finite Girth Corrections

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On a packing and covering problem
• A note on the independence number of triangle-free graphs. II
• Differential equations for random processes and random graphs
• Girth and Independence Ratio
• The Independence Ratio of Regular Graphs