For a graph and partition of its vertex set, an independent transversal of is an independent set of that contains one vertex from each block of . Buys, Kang, and Ozeki studied when a reconfiguration graph on independent transversals of 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 has maximum degree and each block of has size at least , except if the union of some blocks of induces disjoint copies of the complete bipartite graph in . 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.

生成讲解博客的中文版本

生成AI智能校验的中文版本