Random regular graphs of non-constant degree: concentration of the chromatic number
From MaRDI portal
Publication:1043588
DOI10.1016/j.disc.2008.12.014zbMath1182.05105arXivmath/0511343MaRDI QIDQ1043588
Michael Krivelevich, Sonny Ben-Shimon
Publication date: 9 December 2009
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/math/0511343
05C80: Random graphs (graph-theoretic aspects)
05C15: Coloring of graphs and hypergraphs
05C07: Vertex degrees
Related Items
Global maker-breaker games on sparse graphs, On the chromatic number of random \(d\)-regular graphs, Exchangeable pairs, switchings, and random regular graphs
Cites Work
- Small subgraphs of random regular graphs
- On the chromatic number of random graphs
- A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
- A note on the sharp concentration of the chromatic number of random graphs
- Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
- On the independence and chromatic numbers of random regular graphs
- The asymptotic number of labeled graphs with given degree sequences
- The concentration of the chromatic number of random graphs
- Sandwiching random graphs: universality between random graph models
- Random regular graphs of high degree
- Random Regular Graphs of Non-Constant Degree: Independence and Chromatic Number
- Colouring Random Regular Graphs
- On the chromatic number of a random 5-regular graph
- Optimal Construction of Edge-Disjoint Paths in Random Graphs
- Paths in graphs
- On the asymmetry of random regular graphs and random graphs
- Colouring Random 4-Regular Graphs
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- The chromatic number of random graphs
- The chromatic number of random graphs
- The two possible values of the chromatic number of a random graph
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
