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

DOI10.1007/BF02579208zbMath0632.05024WikidataQ105583313 ScholiaQ105583313MaRDI QIDQ1095149

B. George

Publication date: 1987

Published in: Combinatorica (Search for Journal in Brave)

zbMATH Keywords

chromatic numberrandom graphmartingale process

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Coloring of graphs and hypergraphs (05C15)

Related Items (51)

The symmetry in the martingale inequality ⋮ Phase transitions in discrete structures ⋮ Connectedness of graphs generated by a random d-process ⋮ Tree/endofunction bijections and concentration inequalities ⋮ Expose-and-merge exploration and the chromatic number of a random graph ⋮ Concentration of measure and isoperimetric inequalities in product spaces ⋮ Unnamed Item ⋮ Probabilistic constructions in generalized quadrangles ⋮ Complexity of Coloring Random Graphs ⋮ Average-case complexity of backtrack search for coloring sparse random graphs ⋮ The largest hole in sparse random graphs ⋮ On Brooks' Theorem for Sparse Graphs ⋮ Lower bounds on the chromatic number of random graphs ⋮ On the chromatic number of random regular graphs ⋮ On the chromatic number in the stochastic block model ⋮ Two-Point Concentration of the Independence Number of the Random Graph ⋮ The Triangle-Free Process and the Ramsey Number 𝑅(3,𝑘) ⋮ How does the chromatic number of a random graph vary? ⋮ Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022 ⋮ On the concentration of the chromatic number of random graphs ⋮ On the Method of Typical Bounded Differences ⋮ Planting Colourings Silently ⋮ Random graph orders ⋮ On the independence number of random graphs ⋮ Holes in random graphs ⋮ A note on the sharp concentration of the chromatic number of random graphs ⋮ Non-concentration of the chromatic number of a random graph ⋮ On the independence and chromatic numbers of random regular graphs ⋮ On the chromatic number of random graphs ⋮ Spectra, Euclidean representations and clusterings of hypergraphs ⋮ The chromatic number of random graphs ⋮ The chromatic number of random graphs ⋮ Expected values of parameters associated with the minimum rank of a graph ⋮ Unnamed Item ⋮ Local convergence of random graph colorings ⋮ Structure and colour in triangle-free graphs ⋮ Generalized chromatic numbers of random graphs ⋮ On the Number of Solutions in Random Graphk-Colouring ⋮ Independent Sets in Random Graphs from the Weighted Second Moment Method ⋮ Acyclic orientations of random graphs ⋮ On the minimal number of edges in color-critical graphs ⋮ A note on the chromatic number of a dense random graph ⋮ The concentration of the chromatic number of random graphs ⋮ Sharp concentration of the equitable chromatic number of dense random graphs ⋮ The replica symmetric phase of random constraint satisfaction problems ⋮ Independent dominating sets in graphs of girth five ⋮ Two remarks on the Burr-Erdős conjecture ⋮ On the chromatic number of random \(d\)-regular graphs ⋮ Cliques and chromatic number in multiregime random graphs ⋮ On the Concentration of the Domination Number of the Random Graph ⋮ On coupon colorings of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Global versus local asymptotic theories of finite-dimensional normed spaces
• Sequential and distributed graph coloring algorithms with performance analysis in random graph spaces
• On colouring random graphs
• Cliques in random graphs

This page was built for publication: Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)