search
Log In
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
6 votes
242 views

answer given is 4.

Please provide a detailed solution.

in Graph Theory
edited by
242 views
0

4 colors required 

1 2 3 4
A G F D
H C B  
  E    

2 Answers

9 votes

Check this

0 votes

Now to find the chromatic no of the graph we need to find the chromatic partitioning of this graph. 

So, to find chromatic partitioning of a graph G enumerate through all maximal independent set of graph G and take the minimum number of these sets which collectively include all vertices of G.

The maximal independent sets of this graph are

{a,e}, {a,d}, {a,h}, {b,d}, {b,f}.{b,e}, {c,g}, {c,e}, {e,g}.

Now from among these maximal independent set of vertices, we have to select the minimum number of such sets which can include all vertices of the graph and one such way is

{a,d} , {b,f} , {c,e}, {e,g}

This is the chromatic partitioning of this graph and since each one is an independent set we can assign a single color to color all the vertices within an independent set and we need 4 colors to color these 4 sets. So our graph only needs 4 colors for proper coloring

Hence, the chromatic number of this graph is 4.

You can refer to the below question and see the answer by   ma'am and  sir for more reference. 

https://gateoverflow.in/204092/gate2018-18?show=204092#q204092 

  Sir could you please check whether its the right approach or not?

 

Related questions

3 votes
1 answer
3
553 views
How many ways are there to color this graph from any $4$ of the following colors : Violet, Indigo, Blue, Green, Yellow, Orange and Red ? There is a condition that adjacent vertices should not be of the same color I am getting $1680$. Is it correct?
asked Nov 27, 2018 in Graph Theory Balaji Jegan 553 views
0 votes
0 answers
4
383 views
If G is a connected k-regular graph with chromatic number k+1, then find the number of edges in G?
asked Nov 6, 2018 in Graph Theory dan31 383 views
...