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
applies. An undirected graph is called a comparability graph if for every edge
- or
applies.
properties
- Every comparability graph is a perfect graph .
literature
- Reinhard Diestel: graph theory . Springer, 2006, ISBN 3-540-33408-4 .