The Independence Ratio of Regular Graphs

DOI10.2307/2043545zbMath0474.05057MaRDI QIDQ3929774

Béla Bollobás

Publication date: 1981

Published in: Proceedings of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2043545

zbMATH Keywords

girth; independence ratio

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

05C99: Graph theory

Related Items

Bipartite Independence Number in Graphs with Bounded Maximum Degree, Fractional Chromatic Number, Maximum Degree, and Girth, Independent point-set dominating sets in graphs, Mutual information decay for factors of i.i.d., Factor of IID Percolation on Trees, Colouring graphs with forbidden bipartite subgraphs, Graph and hypergraph colouring via nibble methods: a survey, Percolation with small clusters on random graphs, Independent sets in graphs, Induced forests in cubic graphs, Independence ratio and random eigenvectors in transitive graphs, Deterministic local algorithms, unique identifiers, and fractional graph colouring, A note on the independence number of triangle-free graphs. II, On the chromatic number of \(2 K_2\)-free graphs, Packing chromatic number of cubic graphs, Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey, Cubic graphs with small independence ratio, Asymptotic enumeration by degree sequence of graphs of high degree, Graph imperfection. II, Entropy and expansion, Injective edge-coloring of graphs with given maximum degree, Typicality and entropy of processes on infinite trees, Homogeneous sets, clique-separators, critical graphs, and optimal \(\chi\)-binding functions, A note on the independence number, domination number and related parameters of random binary search trees and random recursive trees, Tilings in graphons, Entropy inequalities for factors of IID, Large independent sets in regular graphs of large girth, Maximum independent sets on random regular graphs, Improved replica bounds for the independence ratio of random regular graphs, A tale of two balloons, Matchings in Benjamini–Schramm convergent graph sequences, Locally Dense Independent Sets in Regular Graphs of Large Girth—An Example of a New Approach, Invariant Gaussian processes and independent sets on regular graphs of large girth