Question

The chromatic number and clique number of C'_2k+1(k>3) i.e. complement of odd cycle, are respectively ______

1.   3,2
2.   3,k
3.   k,k
4.   k+1,k

Answer 1

In such questions inductive method often helps ..Say u can verify for smaller graphs..

But here the methodology of finding chromatic number property can be used..As we know for finding chromatic number we begin with the maximal clique as it will require maximum number of colors ..Then we can color the other vertices from the colors that we have used for coloring the maximal clique..

So we verify for n = 7 vertices cycle graph complement ..In that we are able to get K₃ as maximal clique only ..

Therefore for n = 7 vertices clique number = 3

But we are able to color successfully with minimum of 4 colors..

Similarly on verification on n = 9 vertices(not drawing the entire graph as that will be confusing as we will have (⁹C₂ - 9) vertices in the complementary graph..So there we do not get clique of size of 3 but we get clique of size 4..Also we can color with 5 colors only in this case..

So in general for C' _{2k + 1} ,

Chromatic no =  k + 1

Clique no  =  k

Hence 3) should be the correct answer..

Comments

For C'₇ chromatic number = 4. 

---

Corrected.Actually I did not draw the entire graph..My mistake..:)

---

THnaks a lot :-)