The residue of a graph is the number of zeros that remain after repeated application of the Havel-Hakimi process to the degree sequence of a graph. This invariant can be computed efficiently (it is clearly no worse than O(n^2)). The residue is often the best performing of the known lower bounds for the independence number (alpha) of a graph. Its not great – but the lower bound theory is relatively poor compared to the upper bound theory (and Lovasz’s amazing theta function).

Characterizing graphs where alpha = residue is a theoretical challenge and of practical utility. A recognition algorithm for graphs in this class would expand the class of graphs where the independence number can be computed efficiently. These include, for instance, odd cycles $C_{2n+1}$ and the complete bipartite graphs $K_{n,n}$.

- (has_residue_equals_alpha)->((is_regular)->(is_ore))
- (has_residue_equals_alpha)->((is_bipartite)->(is_circular_planar))
- (has_residue_equals_alpha)->((is_regular)->(is_odd_hole_free))
- (has_residue_equals_alpha)->((is_cartesian_product)->(is_regular))
- (has_residue_equals_alpha)->((is_line_graph)->(is_weakly_chordal))
- (has_residue_equals_alpha)->((is_perfect)|(is_eulerian))

- ((has_perfect_matching)&(is_generalized_dirac))->(has_residue_equals_alpha)
- ((is_line_graph)&(is_circular_planar))->(has_residue_equals_alpha)
- (is_chordal)->(has_residue_equals_alpha)
- ((is_even_hole_free)&(is_eulerian))->(has_residue_equals_alpha)

As always counterexamples would be of interest. They will help the program make better conjectures. Proofs would be of interest too!