Projects per year
Abstract
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 semirandom method to prove the following result. For any function urn:xwiley:rsa:media:rsa21051:rsa21051math0001 satisfying urn:xwiley:rsa:media:rsa21051:rsa21051math0002 as urn:xwiley:rsa:media:rsa21051:rsa21051math0003, there is a function urn:xwiley:rsa:media:rsa21051:rsa21051math0004 satisfying urn:xwiley:rsa:media:rsa21051:rsa21051math0005 as urn:xwiley:rsa:media:rsa21051:rsa21051math0006 such that the following holds. For any graph H and any partition of its vertices into parts of size at least urn:xwiley:rsa:media:rsa21051:rsa21051math0007 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:xwiley:rsa:media:rsa21051:rsa21051math0008, 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).
Original language  English 

Number of pages  20 
Journal  Random Structures and Algorithms 
Early online date  13 Oct 2021 
DOIs  
Publication status  Epub ahead of print  13 Oct 2021 
Fingerprint
Dive into the research topics of 'Colorings, transversals, and local sparsity'. Together they form a unique fingerprint.Projects
 1 Finished

Combinatorics, Probability and Algorithms: Fellowship, Establish Career: Professor D Kuhn
Engineering & Physical Science Research Council
1/09/16 → 31/08/21
Project: Research Councils