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.