Skip to main content
3 of 4
added 218 characters in body
Sam Hopkins
  • 24.2k
  • 5
  • 97
  • 171

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 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