edited by
13,009 views
49 votes
49 votes

What is the chromatic number of an $n$ vertex simple connected graph which does not contain any odd length cycle? Assume $n  > 2$.

  1. $2$
  2. $3$
  3. $n-1$   
  4. $n$
edited by

11 Answers

0 votes
0 votes
If n≥ 2 and there are no odd length cycles, Then it is 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.
Answer:

Related questions

54 votes
54 votes
7 answers
9
43 votes
43 votes
4 answers
10
Akash Kanase asked Feb 12, 2016
15,315 views
The minimum number of colours that is sufficient to vertex-colour any planar graph is ________.
46 votes
46 votes
6 answers
11
Kathleen asked Sep 15, 2014
11,046 views
The minimum number of colours required to colour the vertices of a cycle with $n$ nodes in such a way that no two adjacent nodes have the same colour is$2$$3$$4$$n-2 \lef...