Independent transversals in locally sparse graphs

Let G be a graph with maximum degree A whose vertex set is partitioned into parts V(G) V-1 U center dot center dot center dot U 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 is not an element of V-i. We prove that for every fixed epsilon > 0, if all part sizes vertical bar V-i vertical bar >= (1 + epsilon)Delta and the local degree of G is o(Delta), then G has an independent transversal for sufficiently large Delta. 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 vertical bar V-i vertical bar >=(1 +epsilon) and local degree o(Delta) guarantee the existence of such a transversal, and we provide a construction that shows this is asymptotically tight. (C) 2007 Elsevier Inc. All rights reserved.