Journal article
A note on graphs of k-colourings
- Abstract:
- 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.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, pdf, 307.5KB, Terms of use)
-
- Publisher copy:
- 10.37236/12853
Authors
+ Engineering and Physical Sciences Research Council
More from this funder
- Funder identifier:
- https://ror.org/0439y7842
- Grant:
- EP/X013642/1
- Publisher:
- Electronic Journal of Combinatorics
- Journal:
- Electronic Journal of Combinatorics More from this journal
- Volume:
- 31
- Issue:
- 4
- Article number:
- P4.48
- Publication date:
- 2024-11-29
- Acceptance date:
- 2024-10-14
- DOI:
- EISSN:
-
1077-8926
- Language:
-
English
- Pubs id:
-
2070723
- Local pid:
-
pubs:2070723
- Deposit date:
-
2025-03-28
- ARK identifier:
Terms of use
- Copyright holder:
- Hogan et al.
- Copyright date:
- 2024
- Rights statement:
- © The authors. Released under the CC BY license (International 4.0).
- Licence:
- CC Attribution (CC BY)
If you are the owner of this record, you can report an update to it here: Report update to this record