Discrete Mathematics & Theoretical Computer Science, Vol 5 (2002)

Font Size:  Small  Medium  Large

Upper bounds on the non-3-colourability threshold of random graphs

Nikolaos Fountoulakis, Colin McDiarmid

Abstract


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 et 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.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page