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$
  • 11
    $\begingroup$ See en.wikipedia.org/wiki/Kneser_graph $\endgroup$ – Andreas Björklund 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$ – Suresh Venkat 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$ – Yoshio Okamoto Dec 6 '11 at 22:03
  • 2
    $\begingroup$ @AndreasBjörklund maybe you should undelete the answer now :) $\endgroup$ – Suresh Venkat 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$ – Hsien-Chih Chang 張顯之 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.