Frozen colourings of bounded degree graphs

Research output: Contribution to journalArticlepeer-review

Standard

Frozen colourings of bounded degree graphs. / Bonamy, Marthe; Bousquet, Nicolas; Perarnau, Guillem.

In: Electronic Notes in Discrete Mathematics, Vol. 68, 17.07.2018, p. 167-172.

Research output: Contribution to journalArticlepeer-review

Harvard

APA

Vancouver

Author

Bonamy, Marthe ; Bousquet, Nicolas ; Perarnau, Guillem. / Frozen colourings of bounded degree graphs. In: Electronic Notes in Discrete Mathematics. 2018 ; Vol. 68. pp. 167-172.

Bibtex

@article{73ee557ba05145e78d7024cca26020c0,
title = "Frozen colourings of bounded degree graphs",
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.",
keywords = "Glauber dynamics, Graph colourings, Random colourings, Recolouring graph",
author = "Marthe Bonamy and Nicolas Bousquet and Guillem Perarnau",
year = "2018",
month = jul,
day = "17",
doi = "10.1016/j.endm.2018.06.029",
language = "English",
volume = "68",
pages = "167--172",
journal = "Electronic Notes in Discrete Mathematics",
issn = "1571-0653",
publisher = "Elsevier",

}

RIS

TY - JOUR

T1 - Frozen colourings of bounded degree graphs

AU - Bonamy, Marthe

AU - Bousquet, Nicolas

AU - Perarnau, Guillem

PY - 2018/7/17

Y1 - 2018/7/17

N2 - 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.

AB - 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.

KW - Glauber dynamics

KW - Graph colourings

KW - Random colourings

KW - Recolouring graph

UR - http://www.scopus.com/inward/record.url?scp=85049890127&partnerID=8YFLogxK

U2 - 10.1016/j.endm.2018.06.029

DO - 10.1016/j.endm.2018.06.029

M3 - Article

AN - SCOPUS:85049890127

VL - 68

SP - 167

EP - 172

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

SN - 1571-0653

ER -