Reconfiguration of List Colourings

Stijn Cambie, Wouter Cames van Batenburg, Daniel W. Cranston, Ross J. Kang · 2025

Read Reconfiguration of List Colourings by Stijn Cambie, Wouter Cames van Batenburg, Daniel W. Cranston, Ross J. Kang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-08020.txt.

Description

Stijn Cambie and co-authors prove, in a 2025 math paper, how far apart two fair paints of one graph can be. Each node holds a private list of paints. A step swaps one node's paint to a free one in its list, with no clash at its links. Lists run one past each node's link count. The team proves that, for a linked graph with top link count at least three, any two fair paints can be morphed one to the other. The path takes at most the square of the node count in steps, if one node can move at all.

Cut one node's list by one and the space can shatter: no path may join two paints. The edge is sharp, a phase shift in the walk's math.

Catalog record

CREATORStijn Cambie, Wouter Cames van Batenburg, Daniel W. Cranston, Ross J. Kang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE94 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-08020

Browse the full library · About the Tower of Babel