Report Number: CS-TR-76-583
Institution: Stanford University, Department of Computer Science
Title: Determining the stability number of a graph
Author: Chvatal, Vaclav
Date: December 1976
Abstract: We formalize certain rules for deriving upper bounds on the stability number of a graph. The resulting system is powerful enough to (i) encompass the algorithms of Tarjan's type and (ii) provide very short proofs on graphs for which the stability number equals the clique-covering number. However, our main result shows that for almost all graphs with a (sufficiently large) linear number of edges, proofs within our system must have at least exponential length.
http://i.stanford.edu/pub/cstr/reports/cs/tr/76/583/CS-TR-76-583.pdf