Geodesic
Upper bounds on the non-3-colourability threshold of random graphs
Discrete mathematics & theoretical computer science, Tome 5 (2002).

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2002_5_a5,
     author = {Fountoulakis, Nikolaos and McDiarmid, Colin},
     title = {Upper bounds on the non-3-colourability threshold of random graphs},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {5},
     year = {2002},
     doi = {10.46298/dmtcs.299},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.299/}
}
TY  - JOUR
AU  - Fountoulakis, Nikolaos
AU  - McDiarmid, Colin
TI  - Upper bounds on the non-3-colourability threshold of random graphs
JO  - Discrete mathematics & theoretical computer science
PY  - 2002
VL  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.299/
DO  - 10.46298/dmtcs.299
LA  - en
ID  - DMTCS_2002_5_a5
ER  - 
%0 Journal Article
%A Fountoulakis, Nikolaos
%A McDiarmid, Colin
%T Upper bounds on the non-3-colourability threshold of random graphs
%J Discrete mathematics & theoretical computer science
%D 2002
%V 5
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.299/
%R 10.46298/dmtcs.299
%G en
%F DMTCS_2002_5_a5
Fountoulakis, Nikolaos; McDiarmid, Colin. Upper bounds on the non-3-colourability threshold of random graphs. Discrete mathematics & theoretical computer science, Tome 5 (2002). doi : 10.46298/dmtcs.299. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.299/

Cité par Sources :