Tight constructions for reconfigurations of independent transversals

Abstract

For a graph $G$ and partition $\mathcal{U}$ of its vertex set, an independent transversal of $(G,\mathcal{U})$ is an independent set of $G$ that contains one vertex from each block of $\mathcal{U}$. Buys, Kang, and Ozeki studied when a reconfiguration graph on independent transversals of $(G,\mathcal{U})$ is connected, meaning any independent transversal can be transformed into any other one through a sequence of one-vertex modifications while always maintaining an independent transversal. Analogous to a theorem of Haxell, they proved that this is the case if $G$ has maximum degree $\Delta$ and each block of $\mathcal{U}$ has size at least $2\Delta$, except if the union of some $k\ge 1$ blocks of $\mathcal{U}$ induces $k$ disjoint copies of the complete bipartite graph $K_{\Delta ,\Delta }$ in $G$. Solving one of their problems, we exactly characterize the partition structure in the latter exceptional instances of their theorem, showing that there is a rich variety of them but they are generated by a simple constructive procedure.

arXiv comment19 pages, 4 figures