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.
No takes yet. Share an insight, caveat, or question.
Vašek Chvátal (1977) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: