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](https://en.wikipedia.org/wiki/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$. Can we prove this, or does it follow from some known result?


As domotorp wrote in the comments, the graph is also called the discrete Borsuk graph. Is something known about its chromatic number?



Kneser graph with overlap
The graph you are interested in is the generalized Kneser graph $KG(2n,n,1)$. The *generalized Kneser graph* $KG(n,r,s)$ has the same vertex set as a Kneser graph $KG(n,r)$ but with two vertices joined by an edge if their intersection has no more than $s$ elements. 


A web search for chromatic numbers of such graphs generates many hits including a paper of [Frankl](http://onlinelibrary.wiley.com/doi/10.1002/jgt.3190090204/full) and one of [Tort](http://www.sciencedirect.com/science/article/pii/0012365X83900584) in which the chromatic number is computed when $s = 1$ under some restrictions on $n$.


