The chromatic number of random regular graphs

DOI10.1007/978-3-540-27821-4_20MaRDI QIDQ5313025zbMATH OpenOpenAlexFDO

Authors Cristopher Moore, D. Achlioptas

Publication date 25 August 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cond-mat/0407278

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Random graphs (graph-theoretic aspects) (05C80)

Abstract: Given any integer d >= 3, let k be the smallest integer such that d < 2k log k. We prove that with high probability the chromatic number of a random d-regular graph is k, k+1, or k+2, and that if (2k-1) log k < d < 2k log k then the chromatic number is either k+1 or k+2.

Recommendations

• On the chromatic number of random regular graphs
• On the chromatic number of random \(d\)-regular graphs
• Colouring Random Regular Graphs
• The two possible values of the chromatic number of a random graph
• On the chromatic number of random graphs

Cited in

(24)

• An upper bound on adaptable choosability of graphs
• On the chromatic number of random \(d\)-regular graphs
• Random regular graphs of non-constant degree: concentration of the chromatic number
• On the independence and chromatic numbers of random regular graphs
• Distinguishing chromatic number of random Cayley graphs
• On the chromatic number of the preferential attachment graph
• Two notions of unit distance graphs
• Lower bounds on the chromatic number of random graphs
• Random regular graphs of high degree
• Hadwiger number and chromatic number for near regular degree sequences
• Regular graphs with prescribed chromatic number
• The t-improper chromatic number of random graphs
• Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models
• The cook-book approach to the differential equation method
• scientific article; zbMATH DE number 2113521 (Why is no real title available?)
• scientific article; zbMATH DE number 861409 (Why is no real title available?)
• Decoding from pooled data: sharp information-theoretic bounds
• The Lovász theta function for random regular graphs and community detection in the hard regime
• Planting colourings silently
• MAX k‐CUT and approximating the chromatic number of random graphs
• The Ising Antiferromagnet and Max Cut on Random Regular Graphs
• The two possible values of the chromatic number of a random graph
• The chromatic number of random graphs
• On the chromatic number of random regular graphs

This page was built for publication: The chromatic number of random regular graphs

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