{"docId":360,"paperId":360,"url":"https:\/\/dmtcs.episciences.org\/360","doi":"10.46298\/dmtcs.360","journalName":"Discrete Mathematics & Theoretical Computer Science","issn":"","eissn":"1365-8050","volume":[{"vid":80,"name":"Vol. 8"}],"section":[],"repositoryName":"Hal","repositoryIdentifier":"hal-00961105","repositoryVersion":1,"repositoryLink":"https:\/\/hal.science\/hal-00961105v1","dateSubmitted":"2015-03-26 16:18:53","dateAccepted":"2015-06-09 14:46:09","datePublished":"2006-01-01 08:00:00","titles":{"en":"On randomly colouring locally sparse graphs"},"authors":["Frieze, Alan","Vera, Juan"],"abstracts":{"en":"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 \u2208 V the average degree of the subgraph H_v induced by the neighbours of v \u2208 V is #x226a \u0394 where \u0394 is the maximum degree and \u0394 >c_1\\ln n then for sufficiently large c_1, this chain mixes rapidly provided q\/\u0394 >\u03b1 , where \u03b1 #x2248 1.763 is the root of \u03b1 = e^\\1\/\u03b1 \\. 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\u0394 \/6 bound of Vigoda for general graphs."},"keywords":[["Counting Colourings"],["Sampling"],["Markov Chains"],"[INFO.INFO-DM] Computer Science [cs]\/Discrete Mathematics [cs.DM]"]}