in Graph Theory edited by
6,310 views
29 votes
29 votes

What is the chromatic number of the following graph?

 

  1. $2$
  2. $3$
  3. $4$
  4. $5$
in Graph Theory edited by
6.3k views

1 comment

some actual colouring :p

5
5

4 Answers

32 votes
32 votes
Best answer

 

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$

edited by

4 Comments

The Four Color theorem

The chromatic number of a planar graph is no greater than four.

Using this we can rule out some option directly. 

10
10

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

How is this information used to solve the given question ? Can someone elaborate on it ? 

0
0
In the given graph , there is a cycle of length 5, 5 is odd, so, at-least 3 colors are needed. Now try to color the vertexes using 3  colors such that no adjacent vertex gets same color(you will be able it using 3 colors)
0
0
3 votes
3 votes

So 3 color used hence chromatic number =3 option B

edited by

3 Comments

answer is $3$ option B)
0
0
Edited Thanks  @reena_kandari
0
0
Is there any problem with answer @puja mishra @rajoramanoj
0
0
2 votes
2 votes

$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)$

2 Comments

What is the independent set here?
0
0

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

0
0
0 votes
0 votes

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

Answer:

Related questions