Abstract
Let G be a graph with maximum degree Δ and k be an integer. The k-recolouring graph of G is the graph whose vertices are proper k-colourings of G and where two colourings are adjacent iff they differ on exactly one vertex. Feghali, Johnson and Paulusma showed that the (Δ+1)-recolouring graph is composed by a unique connected component and (possibly many) isolated vertices, also known as frozen colourings of G. Motivated by its applications to sampling, we study the proportion of frozen colourings of connected graphs. Our main result is that the probability a proper colouring is frozen is exponentially small on the order of the graph. The obtained bound is tight up to a logarithmic factor on Δ in the exponent. We briefly discuss the implications of our result on the study of the Glauber dynamics on (Δ+1)-colourings. Additionally, we show that frozen colourings may exist even for graphs with arbitrary large girth. Finally, we show that typical Δ-regular graphs have no frozen colourings.
Original language | English |
---|---|
Pages (from-to) | 167-172 |
Number of pages | 6 |
Journal | Electronic Notes in Discrete Mathematics |
Volume | 68 |
DOIs | |
Publication status | Published - 17 Jul 2018 |
Keywords
- Glauber dynamics
- Graph colourings
- Random colourings
- Recolouring graph
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics