  A graph class is hereditary if it is closed under vertex deletion. We give
examples of NP-hard, PSPACE-complete and NEXPTIME-complete problems that become
constant-time solvable for every hereditary graph class that is not equal to
the class of all graphs.
