Content deleted Content added
m authorlink rival |
|||
Line 4:
[[Image:Forbidden interval subgraph.svg|thumb|One of the forbidden induced subgraphs of a comparability graph. The generalized cycle
''a''–''b''–''d''–''f''–''d''–''c''–''e''–''c''–''b''–''a'' in this graph has odd length (nine) but has no triangular chords.]]
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 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'').
| |||