Computer Science/Discrete Mathematics Seminar II

Let $G$ be a graph with maximum degree $\Delta$ whose vertex set is partitioned into $r$ parts $V(G)=V_1 \cup \ldots \cup V_r$. An independent transversal is an independent set in $G$ which contains exactly one vertex from each $V_i$. The problem of finding sufficient conditions for the existence of an independent transversal dates back to 1975, when it was raised by Bollob\'as, Erd\H{o}s, and Szemer\'edi. Since then, much work has been done, and this basic concept has also appeared in the study of other combinatorial problems, such as linear arboricity, strong chromatic number and list coloring. Now, define the local degree of $G$ to be the maximum number of neighbors of a vertex $v$ in a part $V_i$, taken over all choices of $V_i$ and $v \not \in V_i$. We prove that for every fixed $\epsilon > 0$, if all part sizes $|V_i|$ are at least $(1+\epsilon)\Delta$ and the local degree of $G$ is $o(\Delta)$, then $G$ has an independent transversal for all sufficiently large $\Delta$. This extends several previous results and settles (in a stronger form) a conjecture of Aharoni and Holzman. Joint work with Benny Sudakov.