GATE2009 q2 - Revision history

Arjun Suresh at 11:34, 15 July 2014

2014-07-15T11:34:57Z

Arjun Suresh at 22:49, 13 July 2014

2014-07-13T22:49:14Z

Arjun Suresh at 16:02, 29 June 2014

2014-06-29T16:02:24Z

Arjun Suresh at 16:01, 29 June 2014

2014-06-29T16:01:47Z

Arjun Suresh: 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 =..."

2014-06-29T16:01:15Z

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 =..."

New page

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

==={{Template:Author|Happy Mittal|{{mittalweb}} }}===
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 <b>(A)</b> is correct.

[[Category: Graph Theory]]
[[Category: GATE2009]]
[[Category: Graph Theory questions]]
[[Category:Discrete Mathematics questions]]

← Older revision		Revision as of 11:34, 15 July 2014
Line 18:		Line 18:

	[[Category: GATE2009]]		[[Category: GATE2009]]
−	[[Category: Graph Theory questions]]	+	[[Category: Graph Theory questions from GATE]]
−	~~[[Category:Discrete Mathematics questions~~]]

@@ Line 16: / Line 16: @@
 {{Template:FBD}}
-[[Category: Graph Theory]]
 [[Category: GATE2009]]
 [[Category: Graph Theory questions]]
 [[Category:Discrete Mathematics questions]]

@@ 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
 		 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.