# independent set and independence number

A set of vertices in a graph $G$ is called an if there are no edges between the vertices.

The independence number of a graph $G$, usually denoted by $\alpha(G)$, is the size of a maximal independent set in $G$. $\alpha(G)\geq\nu$ means that there are $\nu$ vertices with no edges between them.

An independent set is sometimes called a stable set or an anticlique.

Title independent set and independence number IndependentSetAndIndependenceNumber 2013-03-22 14:30:06 2013-03-22 14:30:06 rspuzio (6075) rspuzio (6075) 6 rspuzio (6075) Definition msc 05C69 stable set anticlique Clique2 independent set independence number