edited by
13,002 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
it's even-length cycle graph i.e C2, C4,C6......all need max 2 colour so chromatic number X(G)=2
0 votes
0 votes
Answer : 2

 

Intuition :

If we observe the question,  tree is one of the example which satisfies the requirements of given question.

Now , irrespective of number of nodes, chromatic number of any tree is 2.
0 votes
0 votes
As the Question says that G must not have a odd length cycle then we can simply take any G which has even length cycle say $C_2{}$ , $C_4{}$ ,etc.and solve to get chromatic no as 2.
Answer:

Related questions

54 votes
54 votes
7 answers
1
43 votes
43 votes
4 answers
2
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
3
Kathleen asked Sep 15, 2014
11,045 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...