Question

7. An independent set in a graph G is a subset S C V(G) of vertices of G which are pairwise non-adjacent (i.e., such that there are no edges between any of the vertices in S). Let Q(G) denote the size of the largest independent set in G. Prove that for a graph G with n vertices, GX(G)n- a(G)+ 1.

Answer 1

Solution :

$Since\ each\ color\ class\ (set\ of\ points\ with\ same\ color)\ is\ independent\ set\\ n=\sum |C(x)|\ where\ summation\ is\ taken\ over\ different\ color\ classes.\\|C(x)|\leq\alpha(G).\\\ \\ \therefore n\leq\alpha(G)\times \#of\ different\ color\ classes.\\ \implies n\leq\alpha(G)\times\chi(G)\\\implies\frac{n}{\alpha(G)}\leq\chi(G)\\\\ Now\ since\ we\ can\ color\ the\ maximum\ independent\ set\ vertices\ with\ one\ single\ color\ and\ color\ the\ remaining\\ n-\alpha(G)\ vertices\ with\ different\ colors,\\ \therefore \chi(G)\leq n-\alpha(G)+1$