The Independence Ratio of Regular Graphs

DOI10.2307/2043545zbMath0474.05057OpenAlexW4247615678MaRDI 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

girthindependence ratio

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (05C99)

Related Items (34)

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

This page was built for publication: The Independence Ratio of Regular Graphs