On List Coloring with Separation of the Complete Graph and Set System Intersections

Abstract

We consider the following list coloring with separation problem: Given a graph $G$ and integers $a,b$, find the largest integer $c$ such that for any list assignment $L$ of $G$ with $|L(v)|=a$ for any vertex $v$ and $|L(u)\cap L(v)|\le c$ for any edge $uv$ of $G$, there exists an assignment $\phi$ of sets of integers to the vertices of $G$ such that $\phi (u)\subset L(u)$ and $|\phi (v)|=b$ for any vertex $u$ and $\phi (u)\cap \phi (v)=\varnothing$ for any edge $uv$. Such a value of $c$ is called the separation number of $(G,a,b)$. Using a special partition of a set of lists for which we obtain an improved version of Poincaré's crible, we determine the separation number of the complete graph $K_n$ for some values of $a,b$ and $n$, and prove bounds for the remaining values.

18 pages