Back to Search
Start Over
Paths between colourings of sparse graphs
- Source :
- European Journal of Combinatorics 75 (2019) 169--171
- Publication Year :
- 2018
-
Abstract
- The reconfiguration graph $R_k(G)$ of the $k$-colourings of a graph~$G$ has as vertex set the set of all possible $k$-colourings of $G$ and two colourings are adjacent if they differ on exactly one vertex. We give a short proof of the following theorem of Bousquet and Perarnau (\emph{European Journal of Combinatorics}, 2016). Let $d$ and $k$ be positive integers, $k \geq d + 1$. For every $\epsilon > 0$ and every graph $G$ with $n$ vertices and maximum average degree $d - \epsilon$, there exists a constant $c = c(d, \epsilon)$ such that $R_k(G)$ has diameter $O(n^c)$. Our proof can be transformed into a simple polynomial time algorithm that finds a path between a given pair of colourings in $R_k(G)$.<br />Comment: 3 pages
- Subjects :
- Mathematics - Combinatorics
Computer Science - Discrete Mathematics
05C15
Subjects
Details
- Database :
- arXiv
- Journal :
- European Journal of Combinatorics 75 (2019) 169--171
- Publication Type :
- Report
- Accession number :
- edsarx.1803.03950
- Document Type :
- Working Paper