The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned the same color, is
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
Please let me know where i am getting wrong. !!
$4$ colors are required to color the graph in the prescribed way.
answer = option C
This might help ...
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).
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.
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.