The concentration of the chromatic number of random graphs

DOI10.1007/BF01215914zbMath0910.05058MaRDI QIDQ1280244

Michael Krivelevich, Noga Alon

Publication date: 14 March 1999

Published in: Combinatorica (Search for Journal in Brave)

zbMATH Keywords

chromatic numberrandom graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15)

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

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

This page was built for publication: The concentration of the chromatic number of random graphs