Independent transversals in r-partite graphs Original Research Article

Let G(r,n) denote the set of all r-partite graphs consisting of n vertices in each partite class. An independent transversal of G ∈ G(r,n) is an independent set consisting of exactly one vertex from each vertex class. Let Δ(r,n) be the maximal integer such that every G ∈ G(r,n) with maximal degree less than Δ(r,n) contains an independent transversal. Let Cr = limn→∞ Δ(r,n)/n. We establish the following upper and lower bounds on Cr, provided r > 2: 2⌊log r⌋−12⌊log r⌋−1⩾Cr⩾max{12e, 12⌈log(r3)⌉, 13 · 2⌈log r⌉−3}. For all r > 3, both upper and lower bounds improve upon previously known bounds of Bollobás, Erdős and Szemerédi. In particular, we obtain that C4 = 23, and that limr→∞ Cr ⩾ 1/(2e), where the last bound is a consequence of a lemma of Alon and Spencer. This solves two open problems of Bollobás, Erdős and Szemerédi.