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

Font Size:  Small  Medium  Large
DMTCS vol 5 no 1 (2002), pp. 205-226

Discrete Mathematics & Theoretical Computer Science


Volume 5 n° 1 (2002), pp. 205-226

author:Nikolaos Fountoulakis and Colin McDiarmid
title:Upper bounds on the non-3-colourability threshold of random graphs
keywords:sparse random graphs, 3-colourability, thresholds
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: A Note on the Non-Colourability Threshold of a Random Graph. 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.

If your browser does not display the abstract correctly (because of the different mathematical symbols) you can look it up in the PostScript or PDF files.

reference: Nikolaos Fountoulakis and Colin McDiarmid (2002), Upper bounds on the non-3-colourability threshold of random graphs, Discrete Mathematics and Theoretical Computer Science 5, pp. 205-226
bibtex:For a corresponding BibTeX entry, please consider our BibTeX-file.
ps.gz-source:dm050114.ps.gz (79 K)
ps-source:dm050114.ps (227 K)
pdf-source:dm050114.pdf (204 K)

The first source gives you the `gzipped' PostScript, the second the plain PostScript and the third the format for the Adobe accrobat reader. Depending on the installation of your web browser, at least one of these should (after some amount of time) pop up a window for you that shows the full article. If this is not the case, you should contact your system administrator to install your browser correctly.

Due to limitations of your local software, the two formats may show up differently on your screen. If eg you use xpdf to visualize pdf, some of the graphics in the file may not come across. On the other hand, pdf has a capacity of giving links to sections, bibliography and external references that will not appear with PostScript.

Automatically produced on Mon Nov 4 10:03:11 CET 2002 by ifalk