Problem of the Week
Hilton Memorial Lecture
Threshold graphs have been widely studied because of their simple structure and their role in the theory of degree sequences of graphs. A simple relaxation in the “building-process” definition of threshold graphs leads to a much bigger class, one we call mock threshold graphs. Our main result is a theorem characterizing this class by forbidden induced subgraphs: A graph is mock threshold if and only if it contains neither a cycle of length at least 5, nor its complement, and nor any of a specific set of 318 small graphs. (The notion of containment here is that of induced subgraphs.) This is in stark contrast with threshold graphs, where the forbidden set has only three members.
This is joint work with Richard Behr and Thomas Zaslavsky.
We can also characterize mock threshold graphs that are claw-free, or line graphs, or some other kinds of graph.