Skip to main content
3 of 8
deleted 108 characters in body
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.

Edit: As pointed out by Aaron Dall below, this corresponds to the generalized Kneser graph $KG(2n,n,1)$. Has its chromatic number been studied.

pi66
  • 1.2k
  • 8
  • 18