Geodesic
A note on the non-colorability threshold of a random graph
The electronic journal of combinatorics, Tome 7 (2000)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

In this paper we consider the problem of establishing a value $r_0$ such that almost all random graphs with $n$ vertices and $rn$ edges, $r > r_0$, are asymptotically not 3-colorable. In our approach we combine the concept of rigid legal colorings introduced by Achlioptas and Molloy with the occupancy problem for random allocations of balls into bins. Using the sharp estimates obtained by Kamath et al. of the probability that no bin is empty after the random placement of the balls and exploiting the relationship between the placement of balls and the rigid legal colorings, we improve the value $r_0 = 2.522$ previously obtained by Achlioptas and Molloy to $r_0 = 2.495$.
DOI : 10.37236/1507
Classification : 05C80, 05C15
Mots-clés : non-colorability, random graphs, colorings, occupancy problem 
@article{10_37236_1507,
     author = {Alexis C. Kaporis and Lefteris M. Kirousis and Yannis C. Stamatiou},
     title = {A note on the non-colorability threshold of a random graph},
     journal = {The electronic journal of combinatorics},
     year = {2000},
     volume = {7},
     doi = {10.37236/1507},
     zbl = {0939.05073},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1507/}
}
TY  - JOUR
AU  - Alexis C. Kaporis
AU  - Lefteris M. Kirousis
AU  - Yannis C. Stamatiou
TI  - A note on the non-colorability threshold of a random graph
JO  - The electronic journal of combinatorics
PY  - 2000
VL  - 7
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1507/
DO  - 10.37236/1507
ID  - 10_37236_1507
ER  - 
%0 Journal Article
%A Alexis C. Kaporis
%A Lefteris M. Kirousis
%A Yannis C. Stamatiou
%T A note on the non-colorability threshold of a random graph
%J The electronic journal of combinatorics
%D 2000
%V 7
%U http://geodesic.mathdoc.fr/articles/10.37236/1507/
%R 10.37236/1507
%F 10_37236_1507
Alexis C. Kaporis; Lefteris M. Kirousis; Yannis C. Stamatiou. A note on the non-colorability threshold of a random graph. The electronic journal of combinatorics, Tome 7 (2000). doi: 10.37236/1507

Cité par Sources :