Geodesic
On randomly colouring locally sparse graphs
Discrete mathematics & theoretical computer science, Tome 8 (2006).

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

We consider the problem of generating a random q-colouring of a graph G=(V,E). We consider the simple Glauber Dynamics chain. We show that if for all v ∈ V the average degree of the subgraph H_v induced by the neighbours of v ∈ V is #x226a Δ where Δ is the maximum degree and Δ >c_1\ln n then for sufficiently large c_1, this chain mixes rapidly provided q/Δ >α , where α #x2248 1.763 is the root of α = e^\1/α \. For this class of graphs, which includes planar graphs, triangle free graphs and random graphs G_\n,p\ with p #x226a 1, this beats the 11Δ /6 bound of Vigoda for general graphs. 
@article{DMTCS_2006_8_a1,
     author = {Frieze, Alan and Vera, Juan},
     title = {On randomly colouring locally sparse graphs},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {8},
     year = {2006},
     doi = {10.46298/dmtcs.360},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.360/}
}
TY  - JOUR
AU  - Frieze, Alan
AU  - Vera, Juan
TI  - On randomly colouring locally sparse graphs
JO  - Discrete mathematics & theoretical computer science
PY  - 2006
VL  - 8
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.360/
DO  - 10.46298/dmtcs.360
LA  - en
ID  - DMTCS_2006_8_a1
ER  - 
%0 Journal Article
%A Frieze, Alan
%A Vera, Juan
%T On randomly colouring locally sparse graphs
%J Discrete mathematics & theoretical computer science
%D 2006
%V 8
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.360/
%R 10.46298/dmtcs.360
%G en
%F DMTCS_2006_8_a1
Frieze, Alan; Vera, Juan. On randomly colouring locally sparse graphs. Discrete mathematics & theoretical computer science, Tome 8 (2006). doi : 10.46298/dmtcs.360. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.360/

Cité par Sources :