Nikolaos Fountoulakis ; Colin McDiarmid - Upper bounds on the non-3-colourability threshold of random graphs

dmtcs:299 - Discrete Mathematics & Theoretical Computer Science, January 1, 2002, Vol. 5 - https://doi.org/10.46298/dmtcs.299
Upper bounds on the non-3-colourability threshold of random graphsArticle

Authors: Nikolaos Fountoulakis 1; Colin McDiarmid

  • 1 Mathematical Institute [Oxford]

We present a full analysis of the expected number of 'rigid' 3-colourings of a sparse random graph. This shows that, if the average degree is at least 4.99, then as n → ∞ the expected number of such colourings tends to 0 and so the probability that the graph is 3-colourable tends to 0. (This result is tight, in that with average degree 4.989 the expected number tends to ∞.) This bound appears independently in Kaporis \textitet al. [Kap]. We then give a minor improvement, showing that the probability that the graph is 3-colourable tends to 0 if the average degree is at least 4.989.


Volume: Vol. 5
Published on: January 1, 2002
Imported on: March 26, 2015
Keywords: thresholds,sparse random graphs,3-colourability,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 234 times.
This article's PDF has been downloaded 208 times.