in Graph Theory edited by
9,730 views
31 votes
31 votes

The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned the same color, is

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

4 Comments

graph is planar so we can directly say it requires not more than 4 color

this graph has also odd length cycle for that 3 color requires

also this graph has even length cycle for that 2 color 

but i have a doubt here :

if graph is very complex and if both the even and odd length cycle appears as well as planar solution then whts the correct aproach to find color requirement in graph 

same situation with this https://gateoverflow.in/3263/gate2008-it-3

@Bikram sir which approach ?pls help

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

We can use this approach here.

as it is maximum 4 , then 4 colors require for complex kind of graphs where both the even and odd length cycle appears as well as planar solution ..
7
7

I am getting answer as 3. Please let me know where I am getting wrong..!!Please let me know where i am getting wrong. !!

0
0
Two adjacent vertex have got same color (C1)
1
1

5 Answers

33 votes
33 votes
Best answer

$4$ colors are required to color the graph in the prescribed way.

answer = option C

edited by

4 Comments

So we know four color theorem which say any planar graph will be 4 colorable. So this graph is planar so max color required will be 4. Now to strect it you take 3 color and try to color every vertices and you will find definetely 3 is not enough in here so answer is 4.
0
0

@Hemant Parihar

Look, Theorem 5.10.6 (Five Color Theorem)

Every planar graph can be colored with 5 colors.

REF : https://www.whitman.edu/mathematics/cgt_online/book/section05.10.html

0
0
edited by

ASNR1010

bro so its 4 or 5 now?

see here it is saying a planar graph is  4-colorable , 5- colorable as well as 6- colorable.

-> http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2003/MatthewWahab/theorems.html

and I think it is obvious that if a graph is 4 colorable then we can color it easily with more than 4 colors as well (as many vertices it have)!

 

0
0
6 votes
6 votes

Ans C 

by
3 votes
3 votes
note:-The max degree of the vertex is 4 so we need atmost 4 colours to colour the graph

answer is C) 4 only
edited by

1 comment

This is not a correct theorem/result.Counter ex: Degree of every vertex in Graph K5 is 4 (max degree is 4) but we need 5 colors to color the graph.

correct theorem: If every vertex in G has degree at most d then G admits a vertex coloring using d+1 colors. 

3
3
0 votes
0 votes
Since the graph is planar graph it is 4 colorable.

4 Comments

so is it like this that every planar graph can be colored with a maximum of 4 colors and not more than that?

0
0

@Pranavpurkar for any graph with v vertices , we can color it by v color but here we are talking about chromatic number means coloring by minimum color possible.

chromatic number of any planar graph can not be more than 4

 

1
1
0
0
Answer:

Related questions