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
3 votes
544 views

What are the chromatic number of following graphs?

Answer is 6 and 4 respectively.But i am getting 3 for both.

Please someone confirm this?

in Mathematical Logic 544 views
1

The answer which you are getting is for EDGE CHROMATIC number NOT (vertex) CHROMATIC number..

3 Answers

12 votes
 
Best answer

Yes we can color both of them with 3 color so that no two same color is adjacent. but how can we sure that it is not less than 3. As both the graph consist triangle it can't be color with less than 3. So we at least require 3 color to color them.

Moreover they are planer graph, according to four color theorem : The chromatic number of a planar graph is no greater than four.
https://en.wikipedia.org/wiki/Four_color_theorem


selected by
2 votes

yes both of them have 3 chromatic number

–2 votes
3 is the correct answer for both

Related questions

2 votes
0 answers
1
380 views
Let G be a planar Graph Such that every phase is bordered by exactly 3 edges which of the following can never be value for X(G) a)2 b)3 C)4 d)none of these
asked Nov 11, 2017 in Graph Theory Parshu gate 380 views
1 vote
2 answers
2
2 votes
2 answers
4
392 views
Consider a 'reversed Kruskal' Algorithm for computing a MST. Initialize T to be the set of all edges in the graph. Now consider edges from largest to smallest cost. For each edge, delete it from T if that edge belongs to a cycle in T. Assuming all the edge costs are distinct, does this new algorithm correctly compute a MST? a) Yes b) no c) cant say
asked Sep 14, 2017 in Graph Theory Rakshit Gupta 392 views
...