(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 =...")
 
Line 15: Line 15:
  
  
 
+
{{Template:FBD}}
 
[[Category: Graph Theory]]
 
[[Category: Graph Theory]]
 
[[Category: GATE2009]]
 
[[Category: GATE2009]]
 
[[Category: Graph Theory questions]]
 
[[Category: Graph Theory questions]]
 
[[Category:Discrete Mathematics questions]]
 
[[Category:Discrete Mathematics questions]]

Revision as of 16:01, 29 June 2014

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

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

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