1. Kempe Changes in Bounded Treewidth Graphs
- Author
-
Marthe Bonamy, Vincent Delecroix, and Clément Legrand-Duchesne
- Subjects
Combinatorics ,Treewidth ,Polynomial ,Sequence ,Bounded function ,Graph theory ,Graph ,Exponential function ,Mathematics - Abstract
We consider Kempe changes on the k-colourings of a graph on n vertices. If the graph is \((k-1)\)-degenerate, then all its k-colourings are equivalent up to Kempe changes. However, the sequence between two k-colourings that arises from the corresponding proof may be exponential in the number of vertices. An intriguing open question is whether it can be turned polynomial. We prove this to be possible under the stronger assumption that the graph has treewidth at most \(k-1\). Namely, any two k-colourings are equivalent up to \(O(k n^2)\) Kempe changes.
- Published
- 2021
- Full Text
- View/download PDF