Consider a multipartite graph $G$ with maximum degree at most $n-o(n)$, parts $V_1,\ldots,V_k$ have size $|V_i|=n$, and every vertex has at most $o(n)$ neighbors in any part $V_i$. Loh and Sudakov proved that any such $G$ has an independent set, referred to as an ‘independent transversal’, which contains exactly one vertex from each part $V_i$. They further conjectured that the vertex set of $G$ can be decomposed into pairwise disjoint independent transversals. We resolve this conjecture approximately by showing that $G$ contains $n-o(n)$ pairwise disjoint independent transversals. As applications, we give approximate answers to questions on packing list colorings and multipartite Hajnal-Szemerédi theorem. We use probabilistic methods, including a ‘two-layer nibble’ argument. This talk is based on joint work with Tuan Tran.

- All seminars.
- Seminars for 2024

Last updated: 19 Apr 2024