### G-98-71

# Extension of Turán's Theorem to the 2-Stability Number

## , , and BibTeX reference

Given a graph *G* with *n* vertices and stability number (*G*), Turán's theorem gives a lower bound on the number of edges in *G*. Furthermore, Turán has proved that the lower bound is only attained if *G* is the union of (*G*) disjoint balanced cliques. We prove a similar result for the 2-stability number _{2}(*G*) of *G*, which is defined as the largest number of vertices in a 2-colorable subgraph of *G*. Given a graph *G* with *n* vertices and 2-stability number _{2}(*G*), we give a lower bound on the number of edges in *G* and characterize the graphs for which this bound is attained. These graphs are the union of isolated vertices and disjoint balanced cliques. We then derive lower bounds on the 2-stability number, and finally discuss the extension of Turán's theorem to the *q*-stability number, for *q* > 2.

Published **December 1998**
,
13 pages