Large independent sets in regular graphs of large girth

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

Nicholas C. Wormald, Joseph Lauer

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

Independent dominating sets in graphs of girth five, Factor of IID Percolation on Trees, Randomized greedy algorithm for independent sets in regular uniform hypergraphs with large girth, Borel fractional colorings of Schreier graphs, 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, Cubic graphs with small independence ratio, The matching process and independent process in random regular graphs and hypergraphs, Optimal low-degree hardness of maximum independent set, A tale of two balloons, 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