1.8k views

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$
edited | 1.8k views
+5

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

+3
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 ..

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

edited by
0
Practical approach :)
+8
Here we also need to prove that the given graph can't be colored with less than 4 colors.

As it consists cycle with odd vertices it requires at least 3 colors.

But if you try to color them with 3 colors it is not possible to color them with 3 colors.

More ever any planar graph can be colored with 4 colors (Four color theorem).
0

This might help ...

0

If dmax is the maximum degree of a vertex in a graph then the chromatic number of G

k(G) $\leq$ dmax +1

This upper bound can be improved by 1 if the graph G has no complete graph of dmax +1 vertices

so in this case K(G)$\leq$dmax

Since, in this graph dmax=4, atmost 4 colors are needed to color this graph so first eliminate option (d).

Ans C

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

edited by
+2

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.

–1 vote
4 colors
The max degree of the vertex is 4 so we need atleast 5 colours to colour the graph
0
4 colours are enough here !
+1
It is a planar graph so we need only 4 colour.
0

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

But here d+1 is not the min value.