The concentration of the chromatic number of random graphs
From MaRDI portal
Publication:1280244
DOI10.1007/BF01215914zbMath0910.05058MaRDI QIDQ1280244
Michael Krivelevich, Noga Alon
Publication date: 14 March 1999
Published in: Combinatorica (Search for Journal in Brave)
Related Items (36)
Phase transitions in discrete structures ⋮ Information-theoretic thresholds from the cavity method ⋮ Two-point concentration in random geometric graphs ⋮ Unnamed Item ⋮ Complexity of Coloring Random Graphs ⋮ On Two Limit Values of the Chromatic Number of a Random Hypergraph ⋮ Average-case complexity of backtrack search for coloring sparse random graphs ⋮ Lower bounds on the chromatic number of random graphs ⋮ On the chromatic number of random regular graphs ⋮ On the concentration of values of \(j\)-chromatic numbers of random hypergraphs ⋮ One-Point Concentration of the Clique and Chromatic Numbers of the Random Cayley Graph on $\mathbb{F}_2^n$ ⋮ On the chromatic number in the stochastic block model ⋮ Two-Point Concentration of the Independence Number of the Random Graph ⋮ How does the chromatic number of a random graph vary? ⋮ Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022 ⋮ Concentration of rainbow \(k\)-connectivity of a multiplex random graph ⋮ On the concentration of the chromatic number of random graphs ⋮ Planting Colourings Silently ⋮ Non-concentration of the chromatic number of a random graph ⋮ On the chromatic number of random graphs ⋮ On the chromatic numbers of random hypergraphs ⋮ Resilience for the Littlewood-Offord problem ⋮ Local convergence of random graph colorings ⋮ Resilience for the Littlewood-Offord problem ⋮ Induced acyclic tournaments in random digraphs: sharp concentration, thresholds and algorithms ⋮ On the Number of Solutions in Random Graphk-Colouring ⋮ Short proofs of some extremal results III ⋮ Approximability Distance in the Space of H-Colourability Problems ⋮ A note on the chromatic number of a dense random graph ⋮ Sharp concentration of the equitable chromatic number of dense random graphs ⋮ On the chromatic number of random \(d\)-regular graphs ⋮ Random regular graphs of non-constant degree: concentration of the chromatic number ⋮ Cliques and chromatic number in multiregime random graphs ⋮ On the Concentration of the Domination Number of the Random Graph ⋮ A note on the warmth of random graphs with given expected degrees ⋮ Sharp concentration of hitting size for random set systems
Cites Work
- Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
- A note on the sharp concentration of the chromatic number of random graphs
- On the minimal number of edges in color-critical graphs
- Covering the edges of a random graph by cliques
- The chromatic number of random graphs
- The chromatic number of random graphs
- Unnamed Item
- Unnamed Item
This page was built for publication: The concentration of the chromatic number of random graphs
