Skip to main content
2 of 4
add some refs
Russ Woodroofe
  • 3.4k
  • 1
  • 24
  • 22

These are called comparability graphs. 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