GATE IT 2008 | Question: 3

Question

What is the chromatic number of the following graph?

 

• A. $2$
• B. $3$
• C. $4$
• D. $5$

Comments

some actual colouring :p

Answer 1

 

The chromatic number of a graph  is the smallest number of colors needed to color the vertices so that no two adjacent vertices share the same color.

Hence minimum number of colors needed to color given graph is equal to $3$

For odd length cycles we need minimum $3$ colors for vertex coloring and for even length cycles we need just $2$. 

Answer is $B$

Comments

@raja11sep Appel and Haken successfully delivered the proof of the Four Color Theorem in 1976, eliminating it as a conjecture being posed in the 1850s.

---

I think it is the first proof which was proved by computer .

https://en.wikipedia.org/wiki/Computer-assisted_proof#:~:text=In%201976%2C%20the%20four%20color,verified%20using%20a%20computer%20program.

---

thanks

Answer 2

$chromatic\ number(\chi) \ge \frac{total\ number\ of\ vertices(n)}{Independent\ set(\alpha)}$

$n=9\ and\ \alpha=4$

$\chi = \left \lceil \frac{9}{4} \right \rceil = 3$

$and\ also$

 

$so\ it\ cannot\ be\ 4\ and\ answer\ is\ (b)$

Comments

What is the independent set here?

---

R_Ayush777

yellow , green and red vertices are three independent sets here!

Answer 3

So 3 color used hence chromatic number =3 option B

Comments

answer is $3$ option B)

---

Edited Thanks  @reena_kandari

---

Is there any problem with answer @puja mishra @rajoramanoj

Answer 4

hence, 3 colors required. so chromatic no is 3.