Groupe d’études et de recherche en analyse des décisions

G-98-71

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

, et

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.

, 13 pages