Discrete Mathematics & Theoretical Computer Science
| 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.