View source for GATE2009 q2 ← GATE2009 q2

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.

Templates used on this page:

Return to GATE2009 q2.

Retrieved from "https://gatecse.in/wiki/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.