Independent transversals in locally sparse graphs

Let G be a graph with maximum degree Δ whose vertex set is partitioned into parts V ( G ) = V 1 ∪ ⋯ ∪ V r . A transversal is a subset of V ( G ) containing exactly one vertex from each part V i . 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 V i , taken over all choices of V i and v ∉ V i . We prove that for every fixed ϵ > 0 , if all part sizes | V i | ⩾ ( 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 | V i | ⩾ ( 1 + ϵ ) Δ s − 1 and local degree o ( Δ ) guarantee the existence of such a transversal, and we provide a construction that shows this is asymptotically tight.