Randomly Coloring Graphs of Logarithmically Bounded Pathwidth

We consider the problem of sampling a proper k-coloring of a graph of maximal degree ∆ uniformly at random. We describe a new Markov chain for sampling colorings, and show that it mixes rapidly on graphs of logarithmically bounded pathwidth if k ≥ (1+ )∆, for any > 0, using a new hybrid paths argument. ∗California Institute of Technology, Pasadena, CA, 91125, USA. E-mail: svardi@caltech.edu.