Sharp concentration of the chromatic number on random graphs G_n,p
From MaRDI portal
Publication:1095149
Consider the length of an interval containing the chromatic number of a standard random graph \(G_{n,p}\) as \(n\to \infty\). Martingale theory is used to prove asymptotic results for a fixed p and for \(p=n^{-\alpha}\) with \(0<\alpha <1\).
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
Cites work
- Cliques in random graphs
- Global versus local asymptotic theories of finite-dimensional normed spaces
- scientific article; zbMATH DE number 3482343 (Why is no real title available?)
- scientific article; zbMATH DE number 3493681 (Why is no real title available?)
- On colouring random graphs
- Sequential and distributed graph coloring algorithms with performance analysis in random graph spaces
Cited in
(61)- A note on the chromatic number of a dense random graph
- Two remarks on the Burr-Erdős conjecture
- On the chromatic number of random \(d\)-regular graphs
- Expose-and-merge exploration and the chromatic number of a random graph
- Holes in random graphs
- A note on the sharp concentration of the chromatic number of random graphs
- On the independence and chromatic numbers of random regular graphs
- Acyclic orientations of random graphs
- On the minimal number of edges in color-critical graphs
- The concentration of the chromatic number of random graphs
- The symmetry in the martingale inequality
- Phase transitions in discrete structures
- Concentration of measure and isoperimetric inequalities in product spaces
- Structure and colour in triangle-free graphs
- Cliques and chromatic number in multiregime random graphs
- Tree/endofunction bijections and concentration inequalities
- On coupon colorings of graphs
- Probabilistic constructions in generalized quadrangles
- On the concentration of the chromatic number of a random hypergraph
- Lower bounds on the chromatic number of random graphs
- On induced acyclic subgraphs in sparse random digraphs
- Independent sets in random graphs from the weighted second moment method
- Benjamini-Schramm convergence and the distribution of chromatic roots for sparse graphs
- Average-case complexity of backtrack search for coloring sparse random graphs
- scientific article; zbMATH DE number 18981 (Why is no real title available?)
- Connectedness of graphs generated by a random d-process
- Complexity of coloring random graphs: an experimental study of the hardest region
- Generalized chromatic numbers of random graphs
- scientific article; zbMATH DE number 1380613 (Why is no real title available?)
- How Sharp is the Concentration of the Chromatic Number?
- On Brooks' Theorem for Sparse 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
- The triangle-free process and the Ramsey number \(R(3,k)\)
- Non-concentration of the chromatic number of a random graph
- On the number of solutions in random graph \(k\)-colouring
- On the method of typical bounded differences
- Planting colourings silently
- On the concentration of the domination number of the random graph
- The chromatic number of random graphs
- The chromatic number of random graphs
- The largest hole in sparse random graphs
- 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
- On the concentration of the chromatic number of random graphs
- The largest hole in sparse random graphs
- Interview with Joel Spencer
- Interview with Alan Frieze
- Spectra, Euclidean representations and clusterings of hypergraphs
- The clique chromatic number of sparse random graphs
- Independent sets of random trees and sparse random graphs
- Acyclic colorings of graphs with obstructions
- Local convergence of random graph colorings
- On the chromatic number of random regular graphs
- Random graph orders
- On the independence number of random graphs
- On the chromatic number of random graphs
- Expected values of parameters associated with the minimum rank of a graph
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)
