Return to Question

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$. Can we prove this, or does it follow from some known result?

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$. 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?

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$. Can we prove this?

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$. Can we prove this, or does it follow from some known result?