Register

Graph Colouring

1,117 views
9 votes
9 votes

The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned the same color, is

User Avatar

1 Answer

0 votes
0 votes
Answer : 4

Start with the 3-cycle inside the coloring outside vertices with that color from those three colors which it is not adjacent to.

But one moment will come when one outside vertex will adjacent to 3 colored vertices then we need the 4th color.
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

3 votes
3 votes
3 answers
1
rahul sharma 5 asked Jun 12, 2017
1,953 views
[Discrete Maths] Graph Theory Rosen,Chromatic number
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?
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?
User Avatar
2 votes
2 votes
0 answers
2
Parshu gate asked Nov 11, 2017
1,170 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
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
User Avatar
1 votes
1 votes
1 answer
3
suryansh rajput asked Oct 2, 2023
195 views
Graph Theory
User Avatar
3 votes
3 votes
0 answers
4
Kabir5454 asked Jan 2, 2023
448 views
graph theory
Let $G=(V,E)$ where $V=\left \{ 1,2,3,4,.....,150\right \}$ and $(u,v) \in E$ if either $(u mod v) =0$ or $(v mod u)=0$.The Chromatic number of G is ?
Let $G=(V,E)$ where $V=\left \{ 1,2,3,4,.....,150\right \}$ and $(u,v) \in E$ if either $(u mod v) =0$ or $(v mod u)=0$.The Chromatic number of G is ?
User Avatar
Link Copied!