The Gateway to Computer Science Excellence
+16 votes
2.6k views

The chromatic number of the following graph is _____

in Graph Theory by Boss (16.8k points)
edited by | 2.6k views

4 Answers

+32 votes
Best answer

Here, Independent sets, $S_1 = \{a,d\}, S_2 = \{b,e\}, S_3 = \{c,f\}$

Therefore, vertices of $S_1$ has no connection between each other [∵ $a$ & $d$ are not connected by an edge]

$ S_1 ⇒  $put ${\color{red}{RED}}$


Vertices of $S_2$ has no connection between each other [∵ $b$ & $e$ are not connected by an edge]

$ S_2 ⇒  $put ${\color{GREEN}{GREEN}}$


Vertices of $S_3$ has no connection between each other [∵ $c$ & $f$ are not connected by an edge]

$ S_3 ⇒  $put ${\color{BLUE}{BLUE}}$


∴ These graph has chromatic number as $3$.

Explanation: Why solving by independent sets?

Independent set means a set containing vertices & each & every vertex of this set is independent to each other i.e. if there are $3$ vertices in an independent set, then each vertex of this set does not connected to other vertex of this set by an edge.

Suppose, there are two independent sets $(S_1$ & $S_2)$. Then any vertex of $S_1$ has connection(share an edge) to any vertex of set $S_2$.

∵ $S_1,S_2, S_3$ are different independent sets & they share some connection between them, we put different colours to different sets.

$S_1$ share connections to $S_2$ & $S_3$

∴ Put  ${\color{RED}{RED}}$ to $S_1$, not $S_2$ & $S_3$

Similarly, $S_2$ share connections to $S_1$ & $S_3$

∴ Put  ${\color{GREEN}{GREEN}}$ to $S_2$, not $S_1$ & $S_3$

$S_3$ share connections to $S_1$ & $S_2$

∴ Put  ${\color{BLUE}{BLUE}}$ to $S_3$, not $S_1$ & $S_2$

The advantage of following this method is when we have a complicated graph then we do not need to continuously see whether any vertex is adjacent to each other when we colour any vertex.

by Boss (15.2k points)
edited by
0
But the calculation of all independent sets in a graph and especially when the graph is big is not easy.
+1
Yes, but if you practised more, then i think that is not a problem & it doesn't give a wrong answer
+1
Yes, that correct!. This was something I was looking for!. Guaranteed approach with minimum number of colors used.
+2
yes, when I started solving chromatic numbers I's doing mistakes & then learnt this approach, & since then it never gives a wrong answer
0
And the traditional approach of getting the chromatic numbers can give us a wrong answer if we oversee something, but this approach never does.
+12
It involves the concept of chromatic partitioning which says that the proper colouring of graph induces a partitioning of vertices onto the vertices of graph such that each set formed is an independent set.

So, to find chromatic partitioning of a graph G enumerate through all maximal independent set of graph G and take minimum number of these sets which collectively include all vertices of G.

The maximal independet sets of this graph are

{a,d}, {a,f}, {b,e}, {c,f}, {d,e}.

Now from among these maximal independent set of vertices we have to select minimum number of such sets which can include all vertices of graph and one such way is

{a,d} , {b,e} , {c,f}

This is the chromatic partitioning of this graph and since each one is an independent set we can assign a single colour to colour all vertices within a independent set and we need 3 colours to color these 3 sets.So our graph only needs 3 colours for proper colouring.

Hence,the chromatic number of this graph is 3.

You can include this in your answer sukanya.
0
Sukanya das what is the independence number in above independent sets ?
0
The graph in this question is planar or not ?
+10 votes

$3$ is answer. 

by Veteran (62.7k points)
edited by
+5 votes

Answer is 3

by Boss (35.7k points)
+2 votes

Ans is 3

by Boss (10.6k points)
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,644 questions
56,523 answers
195,611 comments
101,287 users