On the chromatic number of random d-regular graphs
From MaRDI portal
Abstract: In this work we show that, for any fixed d, random d-regular graphs asymptotically almost surely can be coloured with k colours, where k is the smallest integer satisfying d<2(k-1)log(k-1). From previous lower bounds due to Molloy and Reed, this establishes the chromatic number to be asymptotically almost surely k-1 or k. If moreover d>(2k-3)log(k-1), then the value k-1 is discarded and thus the chromatic number is exactly determined. Hence we improve a recently announced result by Achlioptas and Moore in which the chromatic number was allowed to take the value k+1. Our proof applies the small subgraph conditioning method to the number of balanced k-colourings, where a colouring is balanced if the number of vertices of each colour is equal.
Recommendations
Cites work
- A note on the sharp concentration of the chromatic number of random graphs
- A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
- Almost all regular graphs are hamiltonian
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Colouring Random 4-Regular Graphs
- Colouring Random Regular Graphs
- scientific article; zbMATH DE number 3134390 (Why is no real title available?)
- scientific article; zbMATH DE number 1342092 (Why is no real title available?)
- scientific article; zbMATH DE number 1540669 (Why is no real title available?)
- scientific article; zbMATH DE number 3205804 (Why is no real title available?)
- On the chromatic number of a random 5-regular graph
- On the chromatic number of random graphs
- On the independence and chromatic numbers of random regular graphs
- Random Regular Graphs of Non-Constant Degree: Independence and Chromatic Number
- Random regular graphs of high degree
- Random regular graphs of non-constant degree: concentration of the chromatic number
- Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
- The chromatic number of random graphs
- The chromatic number of random graphs
- The concentration of the chromatic number of random graphs
Cited in
(24)- Random regular graphs of non-constant degree: concentration of the chromatic number
- On the number of regular configurations
- On the independence and chromatic numbers of random regular graphs
- Counting colorings of a regular graph
- Lower bounds on the chromatic number of random graphs
- On the chromatic number of a random 5-regular graph
- The chromatic number of random graphs for most average degrees
- The acyclic edge chromatic number of a random d‐regular graph is d + 1
- scientific article; zbMATH DE number 2113521 (Why is no real title available?)
- scientific article; zbMATH DE number 861409 (Why is no real title available?)
- The Lovász theta function for random regular graphs and community detection in the hard regime
- Satisfiability thresholds for regular occupation problems
- On the number of solutions in random graph \(k\)-colouring
- The Lovász theta function for random regular graphs and community detection in the hard regime
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Planting colourings silently
- On the Chromatic Number of Random Graphs with a Fixed Degree Sequence
- Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
- Colorings of the \(d\)-regular infinite tree
- The fractional chromatic number of random graphs
- Satisfiability thresholds for regular occupation problems
- Randomly twisted hypercubes: between structure and randomness
- On the Potts antiferromagnet on random graphs
- On the chromatic number of random regular graphs
This page was built for publication: On the chromatic number of random \(d\)-regular graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1043497)
