search
Log In
25 votes
3.8k views

What is the chromatic number of the following graph?

 

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

some actual colouring :p

4 Answers

30 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
0
how do we differentiate between regular and planar graph to calculate chromatic number.

Like for planar graph we have chromatic number 4. whereas if we have odd cycles chromatic number = 3 else for even it is 2.

Please help.
1
chromatic number of cycle graph if it is planar

3 if n is odd

2 if n is even

chromatic number of wheel graph if it is planar

3 if n is odd

4 if n is even
9

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. 

0

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
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)
2 votes

So 3 color used hence chromatic number =3 option B


edited by
0
answer is $3$ option B)
0
Edited Thanks  @reena_kandari
0
Is there any problem with answer @puja mishra @rajoramanoj
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)$

0 votes

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

Answer:

Related questions

32 votes
4 answers
1
5k views
$G$ is a simple undirected graph. Some vertices of $G$ are of odd degree. Add a node $v$ to $G$ and make it adjacent to each odd degree vertex of $G$. The resultant graph is sure to be regular complete Hamiltonian Euler
asked Oct 28, 2014 in Graph Theory Ishrat Jahan 5k views
44 votes
5 answers
2
5.8k views
Consider the undirected graph $G$ defined as follows. The vertices of $G$ are bit strings of length $n$. We have an edge between vertex $u$ and vertex $v$ if and only if $u$ and $v$ differ in exactly one bit position (in other words, $v$ can be obtained from $u$ by flipping a single bit). ... $\left(\frac{1}{n}\right)$ $\left(\frac{2}{n}\right)$ $\left(\frac{3}{n}\right)$
asked Oct 31, 2014 in Graph Theory Ishrat Jahan 5.8k views
30 votes
5 answers
3
8.1k views
The minimum number of colours that is sufficient to vertex-colour any planar graph is ________.
asked Feb 12, 2016 in Graph Theory Akash Kanase 8.1k views
30 votes
4 answers
4
5.7k 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 \left \lfloor \frac{n}{2} \right \rfloor+2$
asked Sep 15, 2014 in Graph Theory Kathleen 5.7k views
...