Comparability graph

Summary

The comparability graph of a partially ordered set joins two elements by an edge when they are comparable. A graph is a comparability graph when it arises in this way from some partial order. Chains become cliques and antichains become independent sets, so order results such as Mirsky's theorem turn into graph results. Comparability graphs are perfect graphs.