pith. sign in

arxiv: 1403.3370 · v2 · pith:ZOI2WNFFnew · submitted 2014-03-13 · 🧮 math.CO

Choosability with Separation in Complete Multipartite Graphs

classification 🧮 math.CO
keywords choosabilitycompletefracseparationalonassignmentconstantcontext
0
0 comments X
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.