GATE CSE 2009 | Question: 2

Question

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$

Comments

option A is correct it should be 2

---

What is minimum number for EDGE coloring

It depends on the maximum degree of the given graph. If maximum degree of the simple undirected graph is $d_{max}$  , It means we need atleast  $d_{max}$ colors necessarily  to proper color the whole graph but it is not sufficient.We may need  $d_{max} + 1$ colors also for proper edge coloring of the graph but no more than $d_{max} + 1$ colors are required.

Edge chromatic number or chromatic index of any simple undirected graph is either $d_{max}$  or $d_{max} + 1$ according to Vizing's Theorem. 

---

@Shashank shekhar D 1

A wheel graph will have n cycles of length 3, which is odd and not allowed.

Answer 1

it's even-length cycle graph i.e C2, C4,C6......all need max 2 colour so chromatic number X(G)=2

Comments

No its nt ... Question has said that  simple connected graph which does not contain any odd length cycle ...It does nt imply that it has even length cycle ...

---

The question says that does not contain odd- length cycle, it means that it contains even-length cycle or may not contains the even-length cycle,  or contain both of them.(But not Odd length cycle).

Answer 2

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.

Answer 3

given graph is bipartite
every bipartite is 2 colorable
hence 2 is answer

Answer 4

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.