Assume I have a parametrized graph. The parameters are two integers $x$ and $y<x$. Let $S(x)=\{1, \ldots, x\}$. The vertices of the graph are all the subsets of $S(x)$ of size $y$. Two vertices share an edge if their intersection is empty. I need to find the chromatic number of this graph. Is this problem NP-hard ?

Thank you in advance for your help.

  • 11
    $\begingroup$ See en.wikipedia.org/wiki/Kneser_graph $\endgroup$ Dec 6, 2011 at 19:15
  • 2
    $\begingroup$ @AndreasBjörklund actualy I don't think you needed to shift this to a comment: your answer is exactly what the OP needs. $\endgroup$ Dec 6, 2011 at 19:27
  • 3
    $\begingroup$ Andreas pointed out the wikipedia page, and it says the chromatic number is x-2y+2. $\endgroup$ Dec 6, 2011 at 22:03
  • 2
    $\begingroup$ @AndreasBjörklund maybe you should undelete the answer now :) $\endgroup$ Dec 7, 2011 at 3:55
  • 2
    $\begingroup$ Sorry for misunderstanding your question, I should ask you before editing... Despite this, I am still curious about the chromatic index of Kneser graphs. $\endgroup$ Dec 7, 2011 at 4:37

1 Answer 1


See http://en.wikipedia.org/wiki/Kneser_graph


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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