Approximate packing of independent transversals in locally sparse graphs

Abstract

Fix $\epsilon >0$ and consider a multipartite graph $G$ with maximum degree at most $(1-\epsilon )n$, parts $V_1,\dots ,V_k$ of the same size $n$, and where every vertex has at most $o(n)$ neighbors in any part $V_i$. Loh and Sudakov proved that any such $G$ has an independent transversal. They further conjectured that the vertex set of $G$ can be decomposed into pairwise disjoint independent transversals. In the present paper, we resolve this conjecture approximately by showing that $G$ contains $(1-\epsilon )n$ pairwise disjoint independent transversals. As applications, we give approximate answers to questions of Yuster, and of Fischer, Kühn, and Osthus.

minor changes reflecting comments of an anonymous referee