Choosability with Separation in Complete Multipartite Graphs

Abstract

We show that there is a constant $k$ such that when $r\ge 2$ and $m\ge r^k$, the complete $r$-partite graph $K_{m\ast r}$ has a non-colorable list assignment $L$ such that $|L(v)|\ge \frac{7}{750}r\ln m$ for all $v$ and such that $|L(u)\cap L(v)|\le \lfloor \frac{2r}{r-1}\rfloor$ whenever $u\ne v$. This roughly extends a result of Alon to the context of "choosability with separation", introduced by Kratochvíl, Tuza, and Voigt.

This paper has been withdrawn by the author. Withdrawn. It has been pointed out to me that this work has essentially already been done by Furedi-Kostochka-Kumbhat: arXiv:1109.2969