A Reconfigurations Analogue of Brooks' Theorem and its Consequences

Carl Feghali, Matthew Johnson, Daniël Paulusma

Let $G$ be a simple undirected graph on $n$ vertices with maximum degree~$\Delta$. Brooks' Theorem states that $G$ has a $\Delta$-colouring unless~$G$ is a complete graph, or a cycle with an…