Return to Answer

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.

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.

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.

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.

These are called comparability graphs. A forbidden subgraph characterization was given by Gallai in 1967. See the Wikipedia article.

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.