7
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\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
    Commented Jul 14, 2017 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
    Commented Jul 22, 2017 at 20:56

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ Interesting, unfortunately I can't access the papers. Is there a result for the graph $KG(2n,n,1)$? $\endgroup$
    – pi66
    Commented Jul 11, 2017 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
    Commented Jul 11, 2017 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
    Commented Jul 12, 2017 at 10:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .