TIFR CSE 2021 | Part B | Question: 14

Question

Consider the following greedy algorithm for colouring an $n$-vertex undirected graph $G$ with colours $c_{1}, c_{2}, \dots:$ consider the vertices of $G$ in any sequence and assign the chosen vertex the first colour that has not already been assigned to any of its neighbours. Let $m(n, r)$ be the minimum number of edges in a graph that causes this greedy algorithm to use $r$ colours. Which of the following is correct?

• A. $m\left ( n, r \right ) = \Theta \left ( r \right )$
• B. $m\left ( n, r \right ) = \Theta \left ( r\left \lceil \log_{2} \:r \right \rceil \right )$
• C. $m\left ( n, r \right ) = \binom{r}{2}$
• D. $m\left ( n, r \right ) = nr$
• E. $m\left ( n, r \right ) = n\binom{r}{2}$

Answer 1

$\text{option (C). }~m(n,r) = \binom{r}{2}$

An assumption that there’s some order of these $r$ colors,..

to newly selected vertex we’ll assign first color that has not already been assigned to any of its neighbors,

we’ll get a new color only if new node is connected to all the other vertices which have a distinct color assigned to them,

recursively to get $r^{th}$ color , new vertex should be connected to at-least all vertices having $(r-1)$ distinct colors,

minimum value of $m(n,r)$ is given by,

$T(r)=T(r-1) + (r-1) \\ T(1) = 0$

$T(r)=T(r-i) + (r – i) + (r-(i-1)) + … + (r-1) \\ \quad r-i = 1  \Rightarrow i = r -1$

$\text{substituting the value of i, we get}$

$T(r)=T(r-(r-1)) + (r – (r-1)) + (r-(r-2)) + … + (r-1) \\ \quad \quad \Rightarrow T(1) + 1 + 2+ … + (r-1) \\ \quad \quad \Rightarrow 0 + \frac{(r-1)(r-1+1)}{2}  \\ \quad \quad \Rightarrow \frac{r(r-1)}{2} \\ \quad \quad \Rightarrow \binom{r}{c}$

Answer 2

Let us assume that after running the coloring algorithm we obtained the following partitions of the vertex set of the input graph as shown in the image below. In the image below we have partitions of the vertex set of the input graph based upon the color  of the vertex. For an example black partition contains all vertices of the graph which are colored black by the algorithm.

Take two partitions like black and green there will one vertex in black partition and one vertex in green partition such that there is an edge between them.

Observe that there has to be at least one edge between any two color partitions. If there is no edge between them (i.e. one vertex in one partition and second vertex is in second partition) then we can merge these partitions into one which means instead of two colors one could have suffice to color the vertices of the both partitions.

Now it is easy to see that for any two partitions (color classes) there will be an edge. Let p1 and p2 are two partitions then there will be an edge uv such that u is in p1 and v is in p2.

Now it is easy to see that min number of edges needed are (r choose 2).