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.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Achlioptas, D., Moore, C.: Almost all graphs of degree 4 are 3-colorable. Journal of Computer and System Sciences 67(4), 441–471 (2003)
Achlioptas, D., Moore, C.: The asymptotic order of the k-SAT threshold. In: Proc. 43rd Foundations of Computer Science, pp. 779–788 (2002)
Achlioptas, D., Moore, C.: On the two-colorability of random hypergraphs. In: Rolim, J.D.P., Vadhan, S.P. (eds.) RANDOM 2002. LNCS, vol. 2483, pp. 78–90. Springer, Heidelberg (2002)
Achlioptas, D., Naor, A.: The two possible values of the chromatic number of a random graph. In: Proc. 36th Symp. on the Theory of Computing (2004)
Bollobás, B.: Random graphs. Academic Press, London (1985)
Frieze, A., Luczak, T.: On the independence and chromatic numbers of random regular graphs. J. Combin. Theory Ser. B 54, 123–132 (1992)
Janson, S., Lucza, T., Ruciński, A.: Random Graphs. Wiley & Sons, Chichester (2000)
Krza̧ka_la, F., Pagnani, A., Weigt, M.: Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs. Preprint, cond-mat/0403725. Physical Review (to appear)
Luczak, T.: The chromatic number of random graphs. Combinatorica 11(1), 45–54 (1991)
Luczak, T.: A note on the sharp concentration of the chromatic number of random graphs. Combinatorica 11(3), 295–297 (1991)
Molloy, M.: The Chromatic Number of Sparse Random Graphs. Master’s thesis, Faculty of Mathematics, University of Waterloo (1992)
Wormald, N.C.: Models of random regular graphs. In: Lamb, J.D., Preece, D.A. (eds.) Surveys in Combinatorics., London Mathematical Society Lecture Note Series, vol. 276, pp. 239–298. Cambridge University Press, Cambridge (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Achlioptas, D., Moore, C. (2004). The Chromatic Number of Random Regular Graphs. In: Jansen, K., Khanna, S., Rolim, J.D.P., Ron, D. (eds) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. RANDOM APPROX 2004 2004. Lecture Notes in Computer Science, vol 3122. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-27821-4_20
Download citation
DOI: https://doi.org/10.1007/978-3-540-27821-4_20
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22894-3
Online ISBN: 978-3-540-27821-4
eBook Packages: Springer Book Archive