Reconfiguration graphs of $K_{2,3}$-minor-free graphs

Abstract

The $\ell$-reconfiguration graph of a graph $G$, denoted by ${\mathcal{R}}_{\ell }(G)$, is the graph whose vertices are the proper $\ell$-colorings of $G$, with an edge between two colorings if they differ in color on exactly one vertex. For any graph $G$ of treewidth at most $2$, Bousquet and Perarnau showed that ${\mathcal{R}}_{\ell }(G)$ has linear diameter for $\ell \ge 6$. This result was later extended by Bartier, Bousquet, and Heinrich, who proved that ${\mathcal{R}}_5(G)$ also has linear diameter. In this paper, we show that for each $\ell \ge 5$, the $\ell$-reconfiguration graphs of $K_{2,3}$-minor-free graphs, some of which include graphs of treewidth $3$, have linear diameter. As a key step in our proof, we also establish that the $(\ell -1)$-reconfiguration graphs of cactus graphs have linear diameter.