Determining the Stability Number of a Graph.

Certain rules for deriving upper bounds on the stability number of a graph are formalized. The resulting system is powerful enough to 1 encompass the algorithms of Tarjans type and 2 provide very short proofs on graphs for which the stability number equals the clique-covering number. However, the main result shows that for almost all graphs with a sufficiently large linear number of edges, proofs within the system must have at least exponential length.