TIFR CSE 2013 | Part B | Question: 1

Question

Let $G= (V, E)$ be a simple undirected graph on $n$ vertices. A colouring of $G$ is an assignment of colours to each vertex such that endpoints of every edge are given different colours. Let $\chi (G)$ denote the chromatic number of $G$, i.e. the minimum numbers of colours needed for a valid colouring of $G$. A set $B\subseteq V$ is an independent set if no pair of vertices in $B$ is connected by an edge. Let $a(G)$ be the number of vertices in a largest possible independent set in $G$. In the absence of any further information about $G$ we can conclude.

• A. $\chi \left(G\right)\geq a\left(G\right)$
• B. $\chi \left(G\right)\leq  a\left(G\right)$
• C. $a\left(G\right)\geq \frac{n}{\chi \left(G\right)}$
• D. $a\left(G\right)\leq \frac{n}{\chi \left(G\right)}$
• E. None of the above

Comments

If a graph G is properly coloured with $k$ colours, and has the independence number $i$, then the graph G has at maximum $ki$ vertices.

---

Proof: With chromatic number $k$, there will be $k$ colour classes. Each colour class is an independent set in itself. From the definition of independence number, the maximum size of each colour class would be $i$. So, $\text{total vertices}$ $\leq ki$

Answer 1

Independence number : Size of largest maximum independent set$:a\left(G\right)$ (it covers all adjacent vertices)
Chromatic Number : Minimum No. of color required to properly color the graph$:\chi \left(G\right)$

The vertices of $G$ can be partitioned into $\chi \left(G\right)$ monochromatic classes. Each class is an independent set, and hence cannot have size larger than $α\left(G\right).$

$a\left(G\right) \chi \left(G\right) \geq n.$ (It is a theorem),

Option C.
 

Comments

@ A_i_$_h null graph has independence number 0.

---

$G(V,E)$ is given to be a s1mple undirected graph, hence there will not be any self loops, which means there's no edge between a vertex and itself. So, a single vertex will be inside the independent set.

 

---

Hi there, I think the best answer given here needs a little modification. The Independence set contains non-adjacent pair of vertices, not adjacent ones.

Answer 2

(A) χ(G) ≥ a(G) ,counter ex :Cycle graph with n vertices(n is even) has χ(G) = 2 and a(G) = n/2 .Hence (A) is False.

(B)χ(G)≤a(G) ,counter ex :Complete graph with n vertices  has  χ(G) = n and a(G) = 1 .Hence (B) is False.

(C)a(G)≥n/χ(G), is always True.

Theorem: The vertices of G can be partitioned into χ(G) monochromatic classes. Each class is an independent set, and hence cannot have size larger than α(G),
α(G) χ(G) ≥ n or

a(G)≥n/χ(G) .

The correct answer is (C)a(G)≥n/χ(G) 

Answer 3

This question can also be solved using Pigeon-Hole Principle.

[ Following, Set is nothing but independant set( consisting of all colors of same type ). ]

 

     1.Let the no. of Holes be represented by no. of independant sets( colors of same type ) and no. of Pigeons be represented be represented by no. of Vertices.

 

     2.Here we are trying to distribute n Vertices(pigeons) into ϰ independant sets(holes).

 

     3.As the n > ϰ  ∴ there exists atleast one independant set(hole) which has ≽ n/ϰ Vertices(pigeons).

 

     4.All the Vertices within the set are independant(are of same color) so they don’t have any edge between them, so they produce an independant set.

 

  ∴by Pigeon-Hole principle we can say that there exist an independant set having ≽ n/ϰ vertices.

 

 Hence,  a(G) ≥ n/ϰ(G).

Option (C) is correct.

 

Answer 4

I derived the formulae not in the disciplined way.  

the size of max independent set is a(G)

So the number of independent sets in the graph are = n/a(G)

now this conclusion was drawn from a few examples that always  χ(G) >=  n/a(G) 

see because in the graph there can multiple sub-graphs and each sub-graph can have its own independent set. Considering the chromatic number will always be bigger than the number of independent sets, hence the derivation.