232 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 (G)\geq a(G)$
2. $\chi (G)\leq a(G)$
3. $a(G)\geq n/\chi (G)$
4. $a(G)\leq n/\chi (G)$
5. None of the above.
edited | 232 views

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

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 (its a theorem)
option C

answered by Veteran (15.1k points)
selected
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.