Skip to main content
4 of 4
Wayback machine link for stability
David Roberts
  • 35.5k
  • 11
  • 124
  • 349

This is not an answer, but some context.

A somewhat related notion is that of comparability graphs: these are the graphs for which there is a poset $P$ on the vertex set such that $\{x,y\}$ is an edge $\Leftrightarrow$ $x$ and $y$ are comparable in $P$. A forbidden subgraph characterization was given by Gallai in 1967. See the Wikipedia article.

You can find the list of forbidden graphs in these slides (titled "Cover Graphs and Comparability Graphs") on Tom Trotter's page. I think at one point he also had some course notes posted on it; it's also in his book on dimension theory of posets. See also this post on CSTheory stackexchange.

Russ Woodroofe
  • 3.4k
  • 1
  • 24
  • 22