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

Theorem: $\alpha (G)\chi (G)\ge |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
Canonical name	SizeOfMaximalIndependentSetAndChromaticNumber
Date of creation	2013-03-22 14:30:02
Last modified on	2013-03-22 14:30:02
Owner	kshum (5987)
Last modified by	kshum (5987)
Numerical id	10
Author	kshum (5987)
Entry type	Theorem
Classification	msc 05C69
Classification	msc 05C15