The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+3 votes
418 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 by Boss (24.9k points) | 418 views
+1

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

3 Answers

+11 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

by Boss (16.1k points)
selected by
+2 votes

yes both of them have 3 chromatic number

by Boss (12.1k points)
–2 votes
3 is the correct answer for both
by Active (3.5k points)

Related questions

+7 votes
1 answer
7
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,362 questions
55,786 answers
192,411 comments
90,919 users