2014/03/13 by Gregory J. Puleo, Puleo, Gregory J.
Mathematics · #05C15 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C15
paper · pdf · doi:10.48550/arxiv.1403.3370
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
arxiv created 2014/03/21 · arxiv updated 2014/03/24
We show that there is a constant k such that when r ≥ 2 and m ≥ rk, the complete r-partite graph Km*r has a non-colorable list assignment L such that |L(v)| ≥ (7)/(750)rln m for all v and such that |L(u) ∩ L(v)| ≤ \lfloor (2r)/(r-1) \rfloor whenever u ≠ v. This roughly extends a result of Alon to the context of "choosability with separation", introduced by Kratochvíl, Tuza, and Voigt.