Comparability graph: Difference between revisions

Revision as of 19:41, 7 October 2012

Revision as of 11:23, 11 December 2012

Line 1:

In [[graph theory]], a '''comparability graph''' is an [[undirected graph]] that connects pairs of elements that are [[comparability|comparable]] to each other in a [[partial order]]. Comparability graphs have also been called '''transitively orientable graphs''', '''partially orderable graphs''', and '''containment graphs'''.<ref>{{harvtxt|Golumbic|1980}}, p. 105; {{harvtxt|Brandstädt|Le|Spinrad|1999}}, p. 94.</ref>

An '''incomparability graph''' is an [[undirected graph]] that connects pairs of elements that are not [[comparability|comparable]] to each other in a [[partial order]].

==Definitions and characterization==

Line 12:

One can represent any partial order as a family of sets, such that ''x'' &lt; ''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>

Alternatively,<ref>{{harvtxt|Ghouila-Houri|1962}} and {{harvtxt|Gilmore|Hoffman|1964}}. See also {{harvtxt|Brandstädt|Le|Spinrad|1999}}, theorem 6.1.1, p. 91.</ref>, a comparability graph is a graph such that, for every ''generalized cycle'' of odd length, one can find an edge (''x'',''y'') connecting two vertices that are at distance two in the cycle. Such an edge is called a ''triangular chord''. In this context, a generalized cycle is defined to be a [[Glossary of graph theory#Walks|closed walk]] that uses each edge of the graph at most once in each direction.

Comparability graphs can also be characterized by a list of [[forbidden induced subgraph]]s.<ref>{{harvtxt|Gallai|1967}}; {{harvtxt|Trotter|1992}}; {{harvtxt|Brandstädt|Le|Spinrad|1999}}, p. 91 and p. 112.</ref>