Digital-Logic-Design
January 23, 2025Computer-Organization
January 25, 2025GATE 2009
| Question 2 |
What is the chromatic number of an n-vertex simple connected graph which does not contain any odd length cycle? Assume n ≥ 2.
| 2 | |
| 3 | |
| n-1 | |
| n |
Question 2 Explanation:
If n≥ 2 and there are no odd length cycles, then it is a bipartite graph.
A bipartite graph has the chromatic number 2.
Eg: Consider a square, which has 4 edges. It can be represented as bipartite ,with chromatic number 2.
A bipartite graph has the chromatic number 2.
Eg: Consider a square, which has 4 edges. It can be represented as bipartite ,with chromatic number 2.
Correct Answer: A
Question 2 Explanation:
If n≥ 2 and there are no odd length cycles, then it is a bipartite graph.
A bipartite graph has the chromatic number 2.
Eg: Consider a square, which has 4 edges. It can be represented as bipartite ,with chromatic number 2.
A bipartite graph has the chromatic number 2.
Eg: Consider a square, which has 4 edges. It can be represented as bipartite ,with chromatic number 2.
Subscribe
Login
0 Comments