Let G be a graph with maximum degree Δ whose vertex set is partitioned into r parts V(G) = V1 ∪ ... ∪ V r . An independent transversal is an independent set in G which contains exactly one vertex from each Vi. The problem of finding sufficient conditions for the existence of an independent transversal dates back to 1975, when it was raised by Bollobás, Erdös, and Szemerédi. Since then, much work has been done, and this basic concept has also appeared in the study of other combinatorial problems, such as linear arboricity, strong chromatic number and list coloring. Now, define the local degree of G to be 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| are at least (1+ε)Δ and the local degree of G is o(Δ), then G has an independent transversal for all sufficiently large Δ. This extends several previous results and settles (in a stronger form) a conjecture of Aharoni and Holzman.
Joint work with Benny Sudakov.