BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-76-583
       ENTRY:: July 04, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Determining the stability number of a graph
        TYPE:: Technical Report
      AUTHOR:: Chvatal, Vaclav
        DATE:: December 1976
       PAGES:: 42
    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.
       NOTES:: [Adminitrivia V1/Prg/19950704]
         END:: STAN//CS-TR-76-583