333 views

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 ago | 333 views

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).$

$α\left(G\right) \chi \left(G\right) \geq n.$ (its a theorem),
option C.

edited ago
what i think is it should be option d . take the example of a wheel graph. with w4 . it will contain 5 vertices. and its chromatic number will 3.  so 5/3= 1.something . and the independent set . will be one.  the option  does not hold for it i think .

plus take  a complete graph. and apply . independent set = zero. vertex = n . and chromatic number is n.

so c is saying 0>=1. not true.
a(G) be the number of vertices in a largest possible independent set in G.
Independent set w4 will be 2.
ohh got it. i missed that it is vertex. solved using cut set.
Counter ex for option (A) χ(G)≥a(G) , is Cycle graph with n vertices(n is even) has χ(G) = 2 and a(G) = n/2.

So option (A)is wrong.
+1 vote

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