Content deleted Content added
→Relation to other graph families: Mirsky's theorem is now a separate article |
→Definitions and characterization: [[Orientation (graph theory)|orientation] |
||
Line 8:
For any [[strict partial order|strict partially ordered set]] (''S'',<), the '''comparability graph''' of (''S'', <) is the graph (''S'', ⊥) of which the vertices are the elements of ''S'' and the edges are those pairs {''u'', ''v''} of elements such that ''u'' < ''v''. That is, for a partially ordered set, take the [[directed acyclic graph]], apply [[transitive closure]], and remove orientation.
Equivalently, a comparability graph is a graph that has a '''transitive orientation''',<ref>{{harvtxt|Ghouila-Houri|1962}}; see {{harvtxt|Brandstädt|Le|Spinrad|1999}}, theorem 1.4.1, p. 12. Although the orientations coming from partial orders are [[directed acyclic graph|acyclic]], it is not necessary to include acyclicity as a condition of this characterization.</ref> an assignment of directions to the edges of the graph (i.e. an [[Orientation (graph theory)|orientation]] of the graph) such that the [[adjacency relation]] of the resulting [[directed graph]] is [[transitive relation|transitive]]: whenever there exist directed edges (''x'',''y'') and (''y'',''z''), there must exist an edge (''x'',''z'').
One can represent any partial order as a family of sets, such that ''x'' < ''y'' in the partial order whenever the set corresponding to ''x'' is a subset of the set corresponding to ''y''. In this way, comparability graphs can be shown to be equivalent to containment graphs of set families; that is, a graph with a vertex for each set in the family and an edge between two sets whenever one is a subset of the other.<ref>{{harvtxt|Urrutia|1989}}; {{harvtxt|Trotter|1992}}; {{harvtxt|Brandstädt|Le|Spinrad|1999}}, section 6.3, pp. 94–96.</ref>
| |||