Comparability graph

Remarks

Equivalently, $G$ is a comparability graph when its edges can be oriented so that $x \to y$ and $y \to z$ always imply $x \to z$; such an orientation is called transitive. Example: the complete bipartite graph $K_{m,n}$ is the comparability graph of the poset with $m$ minimal elements, $n$ maximal elements, and each minimal element below each maximal element. Non-example: the cycle $C_5$ is not a comparability graph. Its largest clique has $2$ vertices but it needs $3$ colours, while in a comparability graph the clique number equals the chromatic number, by Mirsky's theorem. The cliques of the comparability graph are the chains of $P$, and its independent sets are the antichains of $P$. Different partial orders, such as an order and its dual, can have the same comparability graph.