Register

[Discrete Maths] Graph Theory Rosen,Chromatic number

• recategorized by
2,642 views
3 3 votes

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?

3 Answers

Best answer
12 12 votes

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
Voting & Accepting an answer helps improve the community
← Previous · DSSB_2017Next → · DSSB_2017
← Previous in category · [Discrete Maths] Gra...Next in category → · General Math
Position:
Show:

Related questions

2 2 votes
0 0 answers
1.6k
1.6k views
Parshu gate asked Nov 11, 2017
1,626 views
chromatic number
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
9 9 votes
1 1 answer
2.1k
2.1k views
Mk Utkarsh asked Jan 10, 2018
2,120 views
Graph Colouring
The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned the same color, is
10 10 votes
2 answers 2 answers
2.8k
2.8k views
rahul sharma 5 asked Nov 14, 2017
2,833 views
Discrete maths: Graph theory [Test series]
Consider $G$ be a directed graph whose vertex set is a set numbers from $2$ to $120$. There is an edge from vertex $b$ if $b=K\times a$. Where $K$ is any natural number. ...
3 3 votes
1 answers 1 answer
2.1k
2.1k views
rahul sharma 5 asked Jun 7, 2017
2,100 views
[Discrete Maths] Graph theory
What is the vertex connectivity and edge connectivity of complete graph?Is it n or n-1?