On List Coloring with Separation of the Complete Graph and Set System Intersections
share
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)∩ L(v)|≤ c for any edge uv of G, there exists an assignment φ of sets of integers to the vertices of G such that φ(u)⊂ L(u) and |φ(v)|=b for any vertex u and φ(u)∩φ(v)=∅ 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.
READ FULL TEXT