Frozen colourings of bounded degree graphs

Marthe Bonamy, Nicolas Bousquet, Guillem Perarnau

Research output: Contribution to journalArticlepeer-review

196 Downloads (Pure)

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 languageEnglish
Pages (from-to)167-172
Number of pages6
JournalElectronic Notes in Discrete Mathematics
Volume68
DOIs
Publication statusPublished - 17 Jul 2018

Keywords

  • Glauber dynamics
  • Graph colourings
  • Random colourings
  • Recolouring graph

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Frozen colourings of bounded degree graphs'. Together they form a unique fingerprint.

Cite this