Independent transversals in locally sparse graphs

Let G be a graph with maximum degree Δ whose vertex set is partitioned into parts V(G)=V1∪⋯∪Vr. A transversal is a subset of V(G) containing exactly one vertex from each part Vi. If it is also an independent set, then we call it an independent transversal. The local degree of G is the maximum number of neighbors of a vertex v in a part Vi, taken over all choices of Vi and v∉Vi. We prove that for every fixed ϵ>0, if all part sizes |Vi|⩾(1+ϵ)Δ and the local degree of G is o(Δ), then G has an independent transversal for sufficiently large Δ. This extends several previous results and settles (in a stronger form) a conjecture of Aharoni and Holzman. We then generalize this result to transversals that induce no cliques of size s. (Note that independent transversals correspond to s=2.) In that context, we prove that parts of size and local degree o(Δ) guarantee the existence of such a transversal, and we provide a construction that shows this is asymptotically tight.