Content deleted Content added
→References: fix chapter, add doi |
m Fixed citation wikilink(s) and general fixes, replaced: | journal = Discrete Mathematics → | journal = Discrete Mathematics |
||
Line 6:
[[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 (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'').
Line 118:
| first1 = M. | last1 = Golumbic | first2 = D. | last2 = Rotem | first3 = J. | last3 = Urrutia | author3-link = Jorge Urrutia Galicia
| title = Comparability graphs and intersection graphs
| journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
| volume = 43
| year = 1983
| |||