Craig Larson

*
Degree Sequence Bounds for the Independence Number of a Graph
*

**Abstract:**
The degree sequence of a graph is a list of the degrees of the vertices of the
graph. The *residue* and *annihilation number* are simple invariants
that can be calculated in polynomial time from the degree sequence. They have
been proved to be, respectively, a lower and upper bound for the
*independence number* of the graph. Since the independence number is an
NP-hard invariant, it would be of interest to characterize the classes of
graphs for which equality holds in these bounds; in these cases we would
presumably have new classes of graphs for which we can calculate the
independence number in polynomial time. One of these problems was recently
solved, while the other remains open. The characterization of graphs with
equal independence and annihilation numbers will be described. The
characterization of graphs with equal independence number and residue remains
open.