<p>See <a href="http://en.wikipedia.org/wiki/Kneser_graph">http://en.wikipedia.org/wiki/Kneser_graph</a></p>

CC BY-SA 3.0
2011-12-06T18:58:05.923Z
2011-12-06T18:58:05.923Z
Andreas Björklund
<p>Assume I have a parametrized graph. The parameters are two integers $x$ and $y&lt;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 <strong>chromatic number</strong> of this graph.
Is this problem NP-hard ?</p>

<p>Thank you in advance for your help.</p>

CC BY-SA 3.0
2011-12-06T19:15:33.820Z
See http://en.wikipedia.org/wiki/Kneser_graph
Andreas Björklund
CC BY-SA 3.0
2011-12-06T19:27:04.180Z
@AndreasBjörklund actualy I don't think you needed to shift this to a comment: your answer is exactly what the OP needs.
Suresh Venkat
CC BY-SA 3.0
2011-12-06T19:33:09.280Z
@SureshVenkat The OP asked for the chromatic index, not the chromatic number as I first thought. I don't see anything about the chromatic index in the wikipage, but at any rate it is good to know the name of this graph family.
Andreas Björklund
CC BY-SA 3.0
2011-12-06T20:58:11.263Z
I am sorry, I made a mistake, it is the chromatic number I am looking for. Thank you Andreas.
user7512
CC BY-SA 3.0
2011-12-06T22:03:54.500Z
Andreas pointed out the wikipedia page, and it says the chromatic number is x-2y+2.
Yoshio Okamoto
CC BY-SA 3.0
2011-12-07T03:55:39.993Z
@AndreasBjörklund maybe you should undelete the answer now :)
Suresh Venkat
CC BY-SA 3.0
2011-12-07T04:37:15.073Z
Sorry for misunderstanding your question, I should ask you before editing... Despite this, I am still curious about the chromatic index of Kneser graphs.
Hsien-Chih Chang 張顯之
<cc.complexity-theory><np-hardness><graph-colouring>
Chromatic number of a particular graph
user7512
# Chromatic number of a particular graph

(Asked by: username_0 on 2011-12-06)

Assume I have a parametrized graph. The parameters are two integers $x$ and $ychromatic number of this graph.
Is this problem NP-hard ?

Thank you in advance for your help.

**Tags:** cc.complexity-theory, np-hardness, graph-colouring
> **Comments:**
> **username_1**: See http://en.wikipedia.org/wiki/Kneser_graph  
> **username_2**: @AndreasBjörklund actualy I don't think you needed to shift this to a comment: your answer is exactly what the OP needs.  
> **username_1**: @SureshVenkat The OP asked for the chromatic index, not the chromatic number as I first thought. I don't see anything about the chromatic index in the wikipage, but at any rate it is good to know the name of this graph family.  
> **username_0**: I am sorry, I made a mistake, it is the chromatic number I am looking for. Thank you Andreas.  
> **username_3**: Andreas pointed out the wikipedia page, and it says the chromatic number is x-2y+2.  
> **username_2**: @AndreasBjörklund maybe you should undelete the answer now :)  
> **username_4**: Sorry for misunderstanding your question, I should ask you before editing... Despite this, I am still curious about the chromatic index of Kneser graphs.  

---

## 1 answers

### Answer by username_1 on 2011-12-06. Score: 9 | Accepted answer

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


---

