Comparability graph

The Hasse diagram of a partial order (left) and the associated comparability graph .

A comparability graph is in Graph theory , a graph whose edges an order relation to its node suffice. Comparability graphs are also referred to as transitively orientable graphs .

definition

A directed graph is called a comparability graph if there is a partial order on the vertex set of the graph, so that the relationship for each edge ${\displaystyle (V,E)}$ ${\displaystyle (V,<)}$ ${\displaystyle V}$ ${\displaystyle (u,v)\in E}$

${\displaystyle u<v}$

applies. An undirected graph is called a comparability graph if for every edge ${\displaystyle (V,E)}$ ${\displaystyle \{u,v\}\in E}$

${\displaystyle u<v}$   or   ${\displaystyle v<u}$

applies.

properties

• Every comparability graph is a perfect graph .

literature

• Reinhard Diestel: graph theory . Springer, 2006, ISBN 3-540-33408-4 .