For a graph $G$, the $k$-colouring graph of $G$ has vertices corresponding to proper $k$-colourings of $G$ and edges between colourings that differ at a single vertex. The graph supports the Glauber dynamics Markov chain for $k$-colourings, and has been extensively studied from both extremal and probabilistic perspectives. In this note, we show that for every graph $G$, there exists $k$ such that $G$ is uniquely determined by its $k$-colouring graph, confirming two conjectures of Asgarli, Krehbiel, Levinson and Russell. We further show that no finite family of generalised chromatic polynomials for $G$, which encode induced subgraph counts of its colouring graphs, uniquely determine $G$.
@article{10_37236_12853,
author = {Emma Hogan and Alex Scott and Youri Tamitegama and Jane Tan},
title = {A note on graphs of \(k\)-colourings},
journal = {The electronic journal of combinatorics},
year = {2024},
volume = {31},
number = {4},
doi = {10.37236/12853},
zbl = {1562.05108},
url = {http://geodesic.mathdoc.fr/articles/10.37236/12853/}
}
TY - JOUR
AU - Emma Hogan
AU - Alex Scott
AU - Youri Tamitegama
AU - Jane Tan
TI - A note on graphs of \(k\)-colourings
JO - The electronic journal of combinatorics
PY - 2024
VL - 31
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/12853/
DO - 10.37236/12853
ID - 10_37236_12853
ER -
%0 Journal Article
%A Emma Hogan
%A Alex Scott
%A Youri Tamitegama
%A Jane Tan
%T A note on graphs of \(k\)-colourings
%J The electronic journal of combinatorics
%D 2024
%V 31
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/12853/
%R 10.37236/12853
%F 10_37236_12853
Emma Hogan; Alex Scott; Youri Tamitegama; Jane Tan. A note on graphs of \(k\)-colourings. The electronic journal of combinatorics, Tome 31 (2024) no. 4. doi: 10.37236/12853
