LATIN 2006: Theoretical Informatics
Lecture Notes in Computer Science, 2006, Volume 3887/2006, 665-676, DOI: 10.1007/11682462_61

Randomly Colouring Graphs with Girth Five and Large Maximum Degree

Lap Chi Lau and Michael Molloy

View Related Documents

Abstract

We prove that the Glauber dynamics on the k-colourings of a graph G on n vertices with girth 5 and maximum degree Δ ≥ 1000 log3 n mixes rapidly if k = qΔ and q > β where β= 1.645... is the root of 2-(1-e − 1/β )2 − 2βe  − 1/β = 0.

Fulltext Preview

Image of the first page of the fulltext document