Geodesic
Sparse graphs usually have exponentially many optimal colorings
The electronic journal of combinatorics, Tome 9 (2002)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

A proper coloring of a graph $G=(V,E)$ is called optimal if the number of colors used is the minimal possible; i.e., it coincides with the chromatic number of $G$. We investigate the typical behavior of the number of distinct optimal colorings of a random graph $G(n,p)$, for various values of the edge probability $p=p(n)$. Our main result shows that for every constant $1/3 < a < 2$, most of the graphs in the probability space $G(n,p)$ with $p=n^{-a}$ have exponentially many optimal colorings.
DOI : 10.37236/1643
Classification : 05C80, 05C15
Mots-clés : chromatic number, random graph, optimal colorings 
@article{10_37236_1643,
     author = {Michael Krivelevich},
     title = {Sparse graphs usually have exponentially many optimal colorings},
     journal = {The electronic journal of combinatorics},
     year = {2002},
     volume = {9},
     doi = {10.37236/1643},
     zbl = {0989.05106},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1643/}
}
TY  - JOUR
AU  - Michael Krivelevich
TI  - Sparse graphs usually have exponentially many optimal colorings
JO  - The electronic journal of combinatorics
PY  - 2002
VL  - 9
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1643/
DO  - 10.37236/1643
ID  - 10_37236_1643
ER  - 
%0 Journal Article
%A Michael Krivelevich
%T Sparse graphs usually have exponentially many optimal colorings
%J The electronic journal of combinatorics
%D 2002
%V 9
%U http://geodesic.mathdoc.fr/articles/10.37236/1643/
%R 10.37236/1643
%F 10_37236_1643
Michael Krivelevich. Sparse graphs usually have exponentially many optimal colorings. The electronic journal of combinatorics, Tome 9 (2002). doi: 10.37236/1643

Cité par Sources :