Monday, July 25, 2005

Comparability graphs


Wow~~~Look at these definitions!!

Definition: (first)

A graph G = (V, E) is a comparability graph if there is a transitive orientation of its edges.

Definition: (second)
The comparability graph of a partial order (V,) has node set V, and edge (x, y) whenever xy or yx. G is a comparability if it is the comparability graph of some poset.

Definition: (third)
The comparability graph of a poset P = (X, ≦) is the graph with vertex set X for which vertices x and y are adjacent either xy or yx in P.

I'll keep studying the paper.

No comments: