edited by
4,208 views
26 votes
26 votes

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.

  1. $\chi \left(G\right)\geq a\left(G\right)$
  2. $\chi \left(G\right)\leq  a\left(G\right)$
  3. $a\left(G\right)\geq \frac{n}{\chi \left(G\right)}$
  4. $a\left(G\right)\leq \frac{n}{\chi \left(G\right)}$
  5. None of the above
edited by

4 Answers

Best answer
25 votes
25 votes

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.
 
edited by
6 votes
6 votes

(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) 

0 votes
0 votes

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.

 

0 votes
0 votes

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.

Answer:

Related questions

37 votes
37 votes
4 answers
1