Arjun Suresh (talk | contribs) (Created page with "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 =...") |
Arjun Suresh (talk | contribs) |
||
| (3 intermediate revisions by the same user not shown) | |||
| Line 12: | Line 12: | ||
Chromatic number of a graph is the minimum number of colors required to color all vertices such that no two adjacent | 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 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 <b>(A)</b> is correct. | + | vertices with alternate colors. So, option <b>(A)</b> is correct. |
| + | {{Template:FBD}} | ||
| − | |||
[[Category: GATE2009]] | [[Category: GATE2009]] | ||
| − | [[Category: Graph Theory questions | + | [[Category: Graph Theory questions from GATE]] |
| − | |||
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.
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