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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2002, 5, pp.205-226
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00958983
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : jeudi 13 mars 2014 - 16:56:11
Dernière modification le : mercredi 29 novembre 2017 - 10:26:22
Document(s) archivé(s) le : vendredi 13 juin 2014 - 12:08:05

Fichier

dm050114.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00958983, version 1

Collections

Citation

Nikolaos Fountoulakis, Colin Mcdiarmid. Upper bounds on the non-3-colourability threshold of random graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2002, 5, pp.205-226. 〈hal-00958983〉

Partager

Métriques

Consultations de la notice

81

Téléchargements de fichiers

129