Colorings, transversals, and local sparsity

Motivated both by recently introduced forms of list coloring and by earlier work on independent transversals subject to a local sparsity condition, we use the semi-random method to prove the following result. For any function urn:x-wiley:rsa:media:rsa21051:rsa21051-math-0001 satisfying urn:x-wiley:rsa:media:rsa21051:rsa21051-math-0002 as urn:x-wiley:rsa:media:rsa21051:rsa21051-math-0003, there is a function urn:x-wiley:rsa:media:rsa21051:rsa21051-math-0004 satisfying urn:x-wiley:rsa:media:rsa21051:rsa21051-math-0005 as urn:x-wiley:rsa:media:rsa21051:rsa21051-math-0006 such that the following holds. For any graph H and any partition of its vertices into parts of size at least urn:x-wiley:rsa:media:rsa21051:rsa21051-math-0007 such that (a) for each part the average over its vertices of degree to other parts is at most d, and (b) the maximum degree from a vertex to some other part is at most urn:x-wiley:rsa:media:rsa21051:rsa21051-math-0008, there is guaranteed to be a transversal of the parts that forms an independent set of H. This is a common strengthening of two results of Loh and Sudakov (2007) and Molloy and Thron (2012), each of which in turn implies an earlier result of Reed and Sudakov (2002).