# size of maximal independent set and chromatic number

Let $\alpha(G)$ be the size of the largest independent set in a graph $G$, and $\chi(G)$ the chromatic number of $G$.

$\alpha(G)\chi(G)\geq|G|$.

###### Proof.

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

Title size of maximal independent set and chromatic number SizeOfMaximalIndependentSetAndChromaticNumber 2013-03-22 14:30:02 2013-03-22 14:30:02 kshum (5987) kshum (5987) 10 kshum (5987) Theorem msc 05C69 msc 05C15