# 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 |