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
2 votes
248 views

What is the chromatic number of following graphs?

1)

2)

in Graph Theory 248 views
3
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
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
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.

Related questions

0 votes
3 answers
1
175 views
Which of the following graphs are bipartite? Only $(1)$ Only $(2)$ Only $(2)$ and $(3)$ None of $(1),(2),(3)$ All of $(1),(2),(3)$
asked Feb 11 in Graph Theory Lakshman Patel RJIT 175 views
15 votes
1 answer
3
1.3k views
Consider the undirected graph G defined as follows. The vertices are bit string of length 5. We have an edge between vertex “a” and vertex “b” iff “a” and “b” differ only in one bit possible (i.e., hamming distance1). What is the ratio of chromatic number of G to the diameter of G? Model Question : https://gateoverflow.in/3564/gate2006-it_25
asked Jan 28, 2016 in Graph Theory pC 1.3k views
0 votes
1 answer
4
512 views
I am from a Mechanical background and I am going to give a GATE2017 in cse. I want to know about the mark distribution among the subjects of Maths(like Probabilty, Set theory , Graphs theory, logic etc). I know there is no official distribution but still in average case how it is distributed?
asked Jul 3, 2016 in GATE PieChuckerr 512 views
...