The Gateway to Computer Science Excellence
+2 votes
178 views

What is the chromatic number of following graphs?

1)

2)

in Graph Theory by (215 points) | 178 views
+2
answer already given in inmage
0
Explenation please?
0
Here we have to use brut force method becoz no algo availabke here .just one thing u have to follow that " no adjacent vertex shoukd be of same color"

Follow this approach u will get correct ans .

3 Answers

0 votes
ANSWER are already given but still u want answer .

For 1 option we need  4 colors

For 2 option we need 3 colors
by Boss (20k points)
0
Explenation please?
+1
Here we have to use brute force method becoz no algo available here .just one thing u have to follow that " no adjacent vertex should be of same color"

Follow this approach u will get correct ans
0 votes
Chromatic Number:- Minimum number of color needed to mark every vertices of a graph ,but no two adjacent vertices can have same color

QUESTION :1

Let B be RED

then  W be Blue    G can not be red or blue as then it will be two same color connecting let G YELLOW

R can be BLUE as it is connected with  B and G which has no Blue Color(We could have marked with anyother color ,but we need minimum color number)

Right hand @W can again be YELLOW

 

Inthis way you can progress
by Boss (18k points)
0 votes
https://gateoverflow.in/204092/gate2018-18?show=206903#a206903

Read this answer and this comment:

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

Now for first image, minimum number of independent sets cover entire graph are 4. They are {a,d},{b,c},{g,f},{e,h}. So we need minimum of 4 colours to colour the graph.

For 2nd image, minimum number of independent sets that cover entire graph are 3. They are {a,d,f,h},{b,c,e,i},{g}. So we need minimum of 3 colours to colour the graph.
by Active (3.3k points)

Related questions

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
50,647 questions
56,497 answers
195,493 comments
100,826 users