The two possible values of the chromatic number of a random graph

DOI10.4007/annals.2005.162.1335zbMath1094.05048OpenAlexW1978113428MaRDI QIDQ5920569

Assaf Naor, Demetrios Achlioptas

Publication date: 19 June 2006

Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4007/annals.2005.162.1335

zbMATH Keywords

random graphsbounded degree\(k\)-colorings

Mathematics Subject Classification ID

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

Related Items (59)

Waiter-Client and Client-Waiter planarity, colorability and minor games ⋮ Waiter-client and client-waiter colourability and \(k\)-SAT games ⋮ Energy landscape for large average submatrix detection problems in Gaussian random matrices ⋮ Phase transitions in discrete structures ⋮ The diameter of a random subgraph of the hypercube ⋮ On the strong chromatic number of random hypergraphs ⋮ Random Instances of Problems in NP – Algorithms and Statistical Physics ⋮ Two-point concentration in random geometric graphs ⋮ Maximum independent sets on random regular graphs ⋮ Antiferromagnetic Potts model on the Erdős-Rényi random graph ⋮ On the concentration of the chromatic number of a random hypergraph ⋮ A supernodal formulation of vertex colouring with applications in course timetabling ⋮ On Two Limit Values of the Chromatic Number of a Random Hypergraph ⋮ Estimating the \(r\)-colorability threshold for a random hypergraph ⋮ Upper-bounding the \(k\)-colorability threshold by counting covers ⋮ Lower bounds on the chromatic number of random graphs ⋮ Harnessing the Bethe free energy ⋮ The discrepancy of random rectangular matrices ⋮ On the concentration of values of \(j\)-chromatic numbers of random hypergraphs ⋮ On the chromatic number in the stochastic block model ⋮ Two-Point Concentration of the Independence Number of the Random Graph ⋮ One-step replica symmetry breaking of random regular NAE-SAT. II ⋮ The Triangle-Free Process and the Ramsey Number 𝑅(3,𝑘) ⋮ How does the chromatic number of a random graph vary? ⋮ On the concentration of the chromatic number of random graphs ⋮ Estimating the strong \(r\)-colorability threshold in random hypergraphs ⋮ Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models ⋮ Planting Colourings Silently ⋮ On the strong chromatic number of a random 3-uniform hypergraph ⋮ Non-concentration of the chromatic number of a random graph ⋮ On the chromatic number of random graphs ⋮ On the chromatic numbers of random hypergraphs ⋮ Charting the replica symmetric phase ⋮ Constraining the clustering transition for colorings of sparse random graphs ⋮ Community Detection and Stochastic Block Models ⋮ Spin systems on Bethe lattices ⋮ Between 2- and 3-colorability ⋮ Solution clustering in random satisfiability ⋮ Gibbs measures and phase transitions on sparse random graphs ⋮ Colouring Random Empire Trees ⋮ The typical structure of sparse $K_{r+1}$-free graphs ⋮ Local convergence of random graph colorings ⋮ On the Potts antiferromagnet on random graphs ⋮ Induced acyclic tournaments in random digraphs: sharp concentration, thresholds and algorithms ⋮ The condensation phase transition in random graph coloring ⋮ On the realization of subgraphs of a random graph by diameter graphs in Euclidean spaces ⋮ A note on the chromatic number of a dense random graph ⋮ Approximation algorithms in combinatorial scientific computing ⋮ The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime ⋮ Rigid Colorings of Hypergraphs and Contiguity ⋮ The condensation transition in random hypergraph 2-coloring ⋮ The replica symmetric phase of random constraint satisfaction problems ⋮ 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 ⋮ Speed and concentration of the covering time for structured coupon collectors ⋮ Unnamed Item ⋮ Sharp concentration of hitting size for random set systems ⋮ Decoding from Pooled Data: Sharp Information-Theoretic Bounds

This page was built for publication: The two possible values of the chromatic number of a random graph