Skip to main content
1 of 8
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 iff 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. Has the chromatic number of the modified graph described above also been investigated?

pi66
  • 1.2k
  • 8
  • 18