You do not have permission to edit this page, for the following reason:
You can view and copy the source of this page.
Templates used on 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
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.
GATECSE