4
$\begingroup$

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.

$\endgroup$
7
  • 11
    $\begingroup$ See en.wikipedia.org/wiki/Kneser_graph $\endgroup$ Dec 6 '11 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 '11 at 19:27
  • 3
    $\begingroup$ Andreas pointed out the wikipedia page, and it says the chromatic number is x-2y+2. $\endgroup$ Dec 6 '11 at 22:03
  • 2
    $\begingroup$ @AndreasBjörklund maybe you should undelete the answer now :) $\endgroup$ Dec 7 '11 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 '11 at 4:37
9
$\begingroup$

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

$\endgroup$

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.