# GATE2018-18

3.7k views

The chromatic number of the following graph is _____

edited
0

Why chromatic number can't be $\mathbf{2}$.

I can colour this graph with $2$ colours only.

Colour the vertex $\mathbf c$ and $\mathbf f$ only?

@ankitgupta.1729

0

@JEET

just show me how you can do that,

I'm not able to do this, becoz (c,d) must goes with different third color.

4

@JEET

In any graph, if triangle is present, it means we can't properly color it with less than 3 colors.

a graph is bipartite iff no odd length cycle present in the graph and every bipartite graph is 2-colorable. So, if there is no odd length cycle in the graph then we can color the whole graph with only 2 colors.

But atleast one edge should be presented in the graph.

Because one exception with bipartite graph is that if there is no edge in the graph then that graph will also be called as bipartite graph and for proper coloring of this type of bipartite graph, we need only 1 color.

1
Thanks.
1

Because one exception with bipartite graph is that if there is no edge in the graph then that graph will also be called as bipartite graph and for proper coloring of this type of bipartite graph, we need only 1 color.

@ Sir,

you mean graph with all isolated vertices ?

1

@Aks9639 bhai no sir.. and yes, you are right. :)

0
👍😄

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.

edited
1
But the calculation of all independent sets in a graph and especially when the graph is big is not easy.
2
Yes, but if you practised more, then i think that is not a problem & it doesn't give a wrong answer
3
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.
16
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.

0
Sukanya das what is the independence number in above independent sets ?
0
The graph in this question is planar or not ?
0

@ankitgupta.1729

Sir, Independent set is look like just same as Partitioing method that we generally used for identify Bipartite Graph Problem.

so rather than taking maximal set we can easily figure out by taking 3 boxes and put vertices in same box such that they are not adjacent -> will give guarantee for chromatic number problem isn't it ?

1

@Aks9639

Here, we can easily  determine that we need 3 boxes only but finding chromatic number of a graph is a hard problem if you have a big graph. It is NP-Hard problem.

1) If you have a big graph and someone ask, " can you properly color this graph with 3 colors ? " -- This is a hard problem

2) If you have a big graph and someone ask, " can you color this graph with 2 colors ? " -- This is an easy problem. Here you only need to check whether a given graph is bipartite or not using BFS or DFS which can be done in linear time (polynomial time)

All the things related to chromatic partitioning which Ayush has mentioned  are given in Graph Theory book by Narsingh Deo. You can find more content there related to it and will not take much time. :)

2

Sir,

thanks a lot,

yeah by using 3 colors we need to apply brute force, that's not possible with in Polynomial time.

$3$ is answer.

edited by

Ans is 3

## Related questions

... $7$ nodes (namely A , B, C, D, E, F, G). The Chromatic number of the given graph is?
Let $G$ be a simple undirected graph. Let $T_D$ be a depth first search tree of $G$. Let $T_B$ be a breadth first search tree of $G$. Consider the following statements. No edge of $G$ is a cross edge with respect to $T_D$. (A cross edge in $G$ is between two nodes ... $\mid i-j \mid =1$. Which of the statements above must necessarily be true? I only II only Both I and II Neither I nor II