Large independent sets in regular graphs of large girth

DOI10.1016/j.jctb.2007.02.006zbMath1183.05058OpenAlexW2091166220MaRDI 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 algorithmindependent setdifferential equation methodindependence ratioregular graphs of large girth

Mathematics Subject Classification ID

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

Related Items (23)

Factor of IID Percolation on Trees ⋮ Properties of regular graphs with large girth via local algorithms ⋮ Invariant Gaussian processes and independent sets on regular graphs of large girth ⋮ Independence ratio and random eigenvectors in transitive graphs ⋮ Lower bounds on the independence number of certain graphs of odd girth at least seven ⋮ New lower bounds on independence number in triangle-free graphs in terms of order, maximum degree and girth ⋮ Randomized greedy algorithm for independent sets in regular uniform hypergraphs with large girth ⋮ Algorithmic obstructions in the random number partitioning problem ⋮ Borel fractional colorings of Schreier graphs ⋮ A tale of two balloons ⋮ Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics ⋮ Locally Dense Independent Sets in Regular Graphs of Large Girth—An Example of a New Approach ⋮ Perfect matchings as IID factors on non-amenable groups ⋮ Induced Forests in Regular Graphs with Large Girth ⋮ Cubic graphs with small independence ratio ⋮ Randomized Greedy Algorithms for Independent Sets and Matchings in Regular Graphs: Exact Results and Finite Girth Corrections ⋮ Independent sets in graphs ⋮ Dynamic monopolies for degree proportional thresholds in connected graphs of girth at least five and trees ⋮ Interpolating between bounds on the independence number ⋮ Independent dominating sets in graphs of girth five ⋮ The matching process and independent process in random regular graphs and hypergraphs ⋮ Optimal low-degree hardness of maximum independent set ⋮ Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Large independent sets in regular graphs of large girth