A note on the sharp concentration of the chromatic number of random graphs

DOI10.1007/BF01205080zbMath0771.05091OpenAlexW2060664509MaRDI QIDQ1180430

Tomasz Łuczak

Publication date: 27 June 1992

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01205080

zbMATH Keywords

random graphschromatic numberBernoulli graph

Mathematics Subject Classification ID

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

Related Items

Phase transitions in discrete structures ⋮ Two-point concentration in random geometric graphs ⋮ Unnamed Item ⋮ Complexity of Coloring Random Graphs ⋮ On the concentration of the chromatic number of a random hypergraph ⋮ On Two Limit Values of the Chromatic Number of a Random Hypergraph ⋮ Average-case complexity of backtrack search for coloring sparse random graphs ⋮ Estimating the \(r\)-colorability threshold for a random hypergraph ⋮ On the chromatic number of random regular graphs ⋮ Random I‐colorable graphs ⋮ 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 ⋮ How does the chromatic number of a random graph vary? ⋮ On the concentration of the chromatic number of random graphs ⋮ Planting Colourings Silently ⋮ Unnamed Item ⋮ On the strong chromatic number of a random 3-uniform hypergraph ⋮ The Lov\'asz Theta Function for Random Regular Graphs and Community Detection in the Hard Regime ⋮ Non-concentration of the chromatic number of a random graph ⋮ On the chromatic number of random graphs ⋮ On the chromatic numbers of random hypergraphs ⋮ Between 2- and 3-colorability ⋮ Local convergence of random graph colorings ⋮ Induced acyclic tournaments in random digraphs: sharp concentration, thresholds and algorithms ⋮ On the Number of Solutions in Random Graphk-Colouring ⋮ On the minimal number of edges in color-critical graphs ⋮ The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime ⋮ The concentration of the chromatic number of random graphs ⋮ Two remarks on the Burr-Erdős conjecture ⋮ On the chromatic number of random \(d\)-regular graphs ⋮ Random regular graphs of non-constant degree: concentration of the chromatic number ⋮ On the Concentration of the Domination Number of the Random Graph

Cites Work

• Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)