You do not have permission to edit this page, for the following reason:

The action you have requested is limited to users in one of the groups: Users, Administrators.


You can view and copy the source of this page.

Return to GATE2009 q2.

What is the chromatic number of an $n$ vertex simple connected graph which does not contain any odd length cycle? Assume $n > 2$.

(A) 2

(B) 3

(C) n-1

(D) n

Solution by Happy Mittal[edit]

Chromatic number of a graph is the minimum number of colors required to color all vertices such that no two adjacent vertices are colored with same color. Since here we have no odd cycle, we can color whole graph with only $2$ colors, coloring the vertices with alternate colors. So, option (A) is correct.




blog comments powered by Disqus