The Gateway to Computer Science Excellence
+16 votes

The chromatic number of the following graph is _____

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

4 Answers

+31 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
But the calculation of all independent sets in a graph and especially when the graph is big is not easy.
Yes, but if you practised more, then i think that is not a problem & it doesn't give a wrong answer
Yes, that correct!. This was something I was looking for!. Guaranteed approach with minimum number of colors used.
yes, when I started solving chromatic numbers I's doing mistakes & then learnt this approach, & since then it never gives a wrong answer
And the traditional approach of getting the chromatic numbers can give us a wrong answer if we oversee something, but this approach never does.
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.
Sukanya das what is the independence number in above independent sets ?
The graph in this question is planar or not ?
+9 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,647 questions
56,465 answers
100,303 users