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?

  • $\begingroup$ It seems that this graph always has chromatic number 6. It's easy to see that 6 colors suffice since the vertex set can be written as a disjoint union of two parts each of which induces a Kneser graph with chromatic number 3. Following Lovasz' original proof, my claim would follow if we can also prove that the neighborhood simplicial complex of your graph is 3-connected. This seems to be true but I haven't been able to come up with a proof yet. However it suggests adding the algebraic topology tag. $\endgroup$ – Gjergji Zaimi Jul 14 '17 at 0:43
  • $\begingroup$ This thing has been called the "discrete Borsuk graph" in this unpublished manuscript: dcg.epfl.ch/files/content/sites/dcg/files/users/… For results related to the continuous version, we of course have ams.org/mathscinet-getitem?mr=708798. $\endgroup$ – domotorp Jul 22 '17 at 20:56

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 and one of Tort in which the chromatic number is computed when $s = 1$ under some restrictions on $n$.

  • $\begingroup$ Interesting, unfortunately I can't access the papers. Is there a result for the graph $KG(2n,n,1)$? $\endgroup$ – pi66 Jul 11 '17 at 9:33
  • 3
    $\begingroup$ No, these papers deal with pretty much the opposite regime, where $n$ is exponentially large in $r$. $\endgroup$ – Gjergji Zaimi Jul 11 '17 at 23:31
  • $\begingroup$ pi66: I only had access to the abstracts of those papers when I referenced them. Thanks @Gjergji Zaimi for clarifying the actual content of the papers. $\endgroup$ – Aaron Dall Jul 12 '17 at 10:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.