Sharp concentration of the chromatic number on random graphs G_n,p

DOI10.1007/BF02579208zbMATH Open0632.05024WikidataQ105583313 ScholiaQ105583313MaRDI QIDQ1095149FDOQ1095149

Publication date: 1987

Published in: Combinatorica (Search for Journal in Brave)

Recommendations

A note on the sharp concentration of the chromatic number of random graphs
The concentration of the chromatic number of random graphs
Sharp concentration of the equitable chromatic number of dense random graphs
On the concentration of the chromatic number of a random hypergraph
Random regular graphs of non-constant degree: concentration of the chromatic number
Sharp bounds for the chromatic number of random Kneser graphs
Non-concentration of the chromatic number of a random graph
On the chromatic number of random graphs
On the chromatic number of random graphs

random graph martingale process chromatic number

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

Cites Work

Global versus local asymptotic theories of finite-dimensional normed spaces
Title not available (Why is that?)
On colouring random graphs
Cliques in random graphs
Title not available (Why is that?)
Sequential and distributed graph coloring algorithms with performance analysis in random graph spaces

Cited In (58)

How does the chromatic number of a random graph vary?
The largest hole in sparse random graphs
Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022
On the concentration of the chromatic number of random graphs
Interview with Joel Spencer
Interview with Alan Frieze
Two-Point Concentration of the Independence Number of the Random Graph
Average-case complexity of backtrack search for coloring sparse random graphs
Independent sets in random graphs from the weighted second moment method
Spectra, Euclidean representations and clusterings of hypergraphs
Two remarks on the Burr-Erdős conjecture
The symmetry in the martingale inequality
Independent dominating sets in graphs of girth five
On the chromatic number of random graphs
A note on the sharp concentration of the chromatic number of random graphs
Acyclic orientations of random graphs
Phase transitions in discrete structures
Planting colourings silently
On coupon colorings of graphs
How Sharp is the Concentration of the Chromatic Number?
Local convergence of random graph colorings
Complexity of coloring random graphs: an experimental study of the hardest region
The replica symmetric phase of random constraint satisfaction problems
Tree/endofunction bijections and concentration inequalities
On the concentration of the chromatic number of a random hypergraph
On the chromatic number of random regular graphs
Title not available (Why is that?)
The chromatic number of random graphs
Generalized chromatic numbers of random graphs
Benjamini-Schramm convergence and the distribution of chromatic roots for sparse graphs
On the chromatic number of random \(d\)-regular graphs
On the independence number of random graphs
On the concentration of the domination number of the random graph
Concentration of measure and isoperimetric inequalities in product spaces
Connectedness of graphs generated by a random d-process
Expose-and-merge exploration and the chromatic number of a random graph
On the independence and chromatic numbers of random regular graphs
On the method of typical bounded differences
A note on the chromatic number of a dense random graph
The chromatic number of random graphs
On induced acyclic subgraphs in sparse random digraphs
Holes in random graphs
On the minimal number of edges in color-critical graphs
The concentration of the chromatic number of random graphs
Probabilistic constructions in generalized quadrangles
On the number of solutions in random graph \(k\)-colouring
Random graph orders
The largest hole in sparse random graphs
The triangle-free process and the Ramsey number \(R(3,k)\)
On the chromatic number in the stochastic block model
Sharp concentration of the equitable chromatic number of dense random graphs
Cliques and chromatic number in multiregime random graphs
Non-concentration of the chromatic number of a random graph
Lower bounds on the chromatic number of random graphs
Structure and colour in triangle-free graphs
Expected values of parameters associated with the minimum rank of a graph
Title not available (Why is that?)
On Brooks' Theorem for Sparse Graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1095149)