research unit 1

Publication

Type of publication:Techreport
Entered by:
TitleRandom sampling of colourings of sparse random graphs with a constant number of colours
Bibtex cite IDRACTI-RU1-2007-25
Year published 2007
Month July
Institution R.A.C.T.I.
Note To appear in Theoretical Computer Science Journal
DOI 10.1016/j.tcs.2008.05.008
Keywords alogirthm,sampling colourings,random graphs,spin system
Abstract
In this work we present an efficient algorithm which, with high probability, provides an almost uniform sample from the set of proper $\chi$-colourings of an instance of sparse random graphs $G_n,d/n$, where $\chi=\chi(d)$ is a sufficiently large constant. This work improves, asymptotically, the result of Dyer, Flaxman Frieze and Vigoda in \citeprevious-result where the algorithm proposed there needs at least $\Theta(\frac\log \log n\log \log \log n)$ colours.
Authors
Topics
BibTeXBibTeX
RISRIS
Attachments
 sampling-colouring.pdf Short description of problem, previous work and result

Publication ID32