Colorings, transversals, and local sparsity. Issue 1 (13th October 2021)

• Record Type: Journal Article
• Authors: Kang, Ross J.; Kelly, Tom
• Is Part Of: Random structures & algorithms. Volume 61:Issue 1(2022)
• Page Start: 173
• Page End: 192
• Publication Date: 2021-10-13
• Subjects: conflict choosability -- correspondence coloring -- independent transversals -- list coloring; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21051
• Languages: English
• ISSNs: 1042-9832

Abstract

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 semi‐random method to prove the following result. For any function μ satisfying μ ( d ) = o ( d ) as d → ∞, there is a function λ satisfying λ ( d ) = d + o ( d ) as d → ∞ such that the following holds. For any graph H and any partition of its vertices into parts of size at least λ 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 μ, 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).