Skip to main content
4 of 8
edited tags
pi66
  • 1.2k
  • 8
  • 18

Kneser graph with overlap

Consider a graph with the vertices being all subsets of size $n$ of a set of size $2n$. Two vertices are connected if their overlap has size at most one. What is the chromatic number of this graph?

If we have two vertices connected when the overlap is empty, then this corresponds to the Kneser graph, for which we know the chromatic number for any $n,k$. In this special case $k=n/2$, the chromatic number of the Kneser graph is trivially two. In our case, we have the generalized Kneser graph $KG(2n,n,1)$. It seems that the chromatic number is always $6$ for any $n\geq 2$. How can we prove this?

pi66
  • 1.2k
  • 8
  • 18