Frozen colourings of bounded degree graphs

Research output: Contribution to journalArticle

Authors

Colleges, School and Institutes

External organisations

  • LOMA, Univ. Bordeaux, UMR 5798
  • Université Grenoble Alpes

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.

Details

Original languageEnglish
Pages (from-to)167-172
Number of pages6
JournalElectronic Notes in Discrete Mathematics
Volume68
Publication statusPublished - 17 Jul 2018

Keywords

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