Skip to Main content Skip to Navigation
New interface
Journal articles

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

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 \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.
Document type :
Journal articles
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/hal-00958983
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s Connect in order to contact the contributor
Submitted on : Thursday, March 13, 2014 - 4:56:11 PM
Last modification on : Thursday, November 25, 2021 - 11:12:10 AM
Long-term archiving on: : Friday, June 13, 2014 - 12:08:05 PM

File

dm050114.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Nikolaos Fountoulakis, Colin Mcdiarmid. Upper bounds on the non-3-colourability threshold of random graphs. Discrete Mathematics and Theoretical Computer Science, 2002, Vol. 5, pp.205-226. ⟨10.46298/dmtcs.299⟩. ⟨hal-00958983⟩

Share

Metrics

Record views

468

Files downloads

600