On the independence and chromatic numbers of random regular graphs
From MaRDI portal
Publication:1186131
DOI10.1016/0095-8956(92)90070-EzbMath0771.05088WikidataQ57401594 ScholiaQ57401594MaRDI QIDQ1186131
Publication date: 28 June 1992
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Related Items
Percolation with small clusters on random graphs, Factor of IID Percolation on Trees, Anagram-Free Colourings of Graphs, Adjacency matrices of random digraphs: singularity and anti-concentration, Invariant Gaussian processes and independent sets on regular graphs of large girth, Maximum independent sets on random regular graphs, Counting colorings of triangle-free graphs, Adaptable and conflict colouring multigraphs with no cycles of length three or four, Lower bounds on the chromatic number of random graphs, Subgraph probability of random graphs with specified degrees and applications to chromatic number and connectivity, Occupancy fraction, fractional colouring, and triangle fraction, Graph and hypergraph colouring via nibble methods: a survey, On the chromatic number of random regular graphs, Algorithmic obstructions in the random number partitioning problem, Improved replica bounds for the independence ratio of random regular graphs, Dismantling Sparse Random Graphs, Perfect matchings as IID factors on non-amenable groups, The cook-book approach to the differential equation method, Random regular graphs of high degree, On the Chromatic Number of Random Graphs with a Fixed Degree Sequence, A determinacy approach to Borel combinatorics, Entropy and expansion, Generalized chromatic numbers of random graphs, Large independent sets in random regular graphs, Measurable versions of the Lovász local lemma and measurable graph colorings, Independent dominating sets in graphs of girth five, On the chromatic number of random \(d\)-regular graphs, Random regular graphs of non-constant degree: concentration of the chromatic number, More spectral bounds on the clique and independence numbers, Graph imperfection. II, On decomposing regular graphs into locally irregular subgraphs, Minimal contagious sets in random regular graphs, Sofic homological invariants and the Weak Pinsker Property
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the independence number of random graphs
- Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
- A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
- The asymptotic number of labeled graphs with given degree sequences
- Weighted sums of certain dependent random variables
- Uniform generation of random regular graphs of moderate degree
- On colouring random graphs
- Cliques in random graphs
- The Solution of a Timetabling Problem
- The chromatic number of random graphs
