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

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 2

option A is correct

Answer 3

short trick