← ALB News · curated headline

Supersaturation and reconfiguration diameter of independent transversals

arXiv Mathematics · WORLD · Mathematics · 11/18/2026, 12:00:00 AM

arXiv:2611.21966v1 Announce Type: new Abstract: Consider the collection of independent transversals of a vertex-partitioned graph of maximum degree $\Delta$. It is a classic result that when all parts have size at least $2\Delta$, the collection is nonempty. Recently, it was found that if the parts have size at least $2\Delta+1$, then every pair of independent transversals is connected, within the collection, by a sequence of one-vertex reconfigurations. We prove, among other results, that there are exponentially many independent transversals when the parts have size at least $2\Delta$, and that the reconfiguration diameter is at most linear in the number of parts when the parts have size at least $4\Delta$.

Continue to arXiv Mathematics →

You are being forwarded in 6s — stay on this page