Geodesic
Almost all graphs with 2. 522\(n\) edges are not 3-colorable
The electronic journal of combinatorics, Tome 6 (1999)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

We prove that for $c \geq 2.522$ a random graph with $n$ vertices and $m=cn$ edges is not 3-colorable with probability $1-o(1)$. Similar bounds for non-$k$-colorability are given for $k>3$.
DOI : 10.37236/1461
Classification : 05C80, 05C15 
@article{10_37236_1461,
     author = {Dimitris Achlioptas and Michael Molloy},
     title = {Almost all graphs with 2. 522\(n\) edges are not 3-colorable},
     journal = {The electronic journal of combinatorics},
     year = {1999},
     volume = {6},
     doi = {10.37236/1461},
     zbl = {0919.05056},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1461/}
}
TY  - JOUR
AU  - Dimitris Achlioptas
AU  - Michael Molloy
TI  - Almost all graphs with 2. 522\(n\) edges are not 3-colorable
JO  - The electronic journal of combinatorics
PY  - 1999
VL  - 6
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1461/
DO  - 10.37236/1461
ID  - 10_37236_1461
ER  - 
%0 Journal Article
%A Dimitris Achlioptas
%A Michael Molloy
%T Almost all graphs with 2. 522\(n\) edges are not 3-colorable
%J The electronic journal of combinatorics
%D 1999
%V 6
%U http://geodesic.mathdoc.fr/articles/10.37236/1461/
%R 10.37236/1461
%F 10_37236_1461
Dimitris Achlioptas; Michael Molloy. Almost all graphs with 2. 522\(n\) edges are not 3-colorable. The electronic journal of combinatorics, Tome 6 (1999). doi: 10.37236/1461

Cité par Sources :