Choosability with Separation in Complete Multipartite Graphs
classification
🧮 math.CO
keywords
choosabilitycompletefracseparationalonassignmentconstantcontext
read the original abstract
We show that there is a constant $k$ such that when $r \geq 2$ and $m \geq r^k$, the complete $r$-partite graph $K_{m*r}$ has a non-colorable list assignment $L$ such that $|L(v)| \geq \frac{7}{750}r\ln m$ for all $v$ and such that $|L(u) \cap L(v)| \leq \left\lfloor \frac{2r}{r-1} \right\rfloor$ whenever $u \neq v$. This roughly extends a result of Alon to the context of "choosability with separation", introduced by Kratochv\'il, Tuza, and Voigt.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.