Comparability graph
A comparability graph is a graph in graph theory, meeting the edges of an order relation on its nodes.
Definition
A directed graph is called comparability graph, if a partial order on the set of nodes of the graph is such that for each edge the relationship
Applies. An undirected graph is called comparability graph if for every edge
Applies.
Properties
- Every comparability graph is a perfect graph.
- The coloring problem can be solved on Vergleichbarkeitsgraphen topological sorting with linear cost in the number of nodes and edges.