Editing Perfect graph (section)

===Comparability graphs===
[[File:Poset et graphe de comparabilité.svg|thumb|upright=1.2|The [[Hasse diagram]] of a partially ordered set, and its [[comparability graph]]]]
A [[partially ordered set]] is defined by its set of elements, and a comparison relation <math>\le</math> that is [[reflexive relation|reflexive]] (for all elements <math>x</math>, <math>x\le x</math>), [[antisymmetric relation|antisymmetric]] (if <math>x\le y</math> and <math>y\le x</math>, then <math>x=y</math>, and [[transitive relation|transitive]] (if <math>x\le y</math> and <math>y\le z</math>, then <math>x\le z</math>). Elements <math>x</math> and <math>y</math> are ''comparable'' if <math>x\le y</math> or <math>y\le x</math>, and ''incomparable'' otherwise. For instance, set inclusion (<math>\subseteq</math>) partially orders any [[family of sets]]. The [[comparability graph]] of a partially ordered set has the set elements as its vertices, with an edge connecting any two comparable elements. Its complement is called an ''incomparability graph''. Different partial orders may have the same comparability graph; for instance, reversing all comparisons changes the order but not the graph.{{r|harzheim-2005}}

Finite comparability graphs (and their complementary incomparability graphs) are always perfect.{{r|berge-1967}} A clique, in a comparability graph, comes from a subset of elements that are all pairwise comparable; such a subset is called a [[Chain (order theory)|chain]], and it is [[total order|linearly ordered]] by the given partial order. An independent set comes from a subset of elements no two of which are comparable; such a subset is called an [[antichain]]. For instance, in the illustrated partial order and comparability graph, <math>\{A,B,C\}</math> is a chain in the order and a clique in the graph, while <math>\{C,D\}</math> is an antichain in the order and an independent set in the graph. Thus, a coloring of a comparability graph is a partition of its elements into antichains, and a clique cover is a partition of its elements into chains. [[Dilworth's theorem]], in the theory of partial orders, states that for every finite partial order, the size of the largest antichain equals the minimum number of chains into which the elements can be partitioned. In the language of graphs, this can be stated as: every finite comparability graph is perfect. Similarly, [[Mirsky's theorem]] states that for every finite partial order, the size of the largest chain equals the minimum number of antichains into which the elements can be partitioned, or that every finite incomparability graph is perfect. These two theorems are equivalent via the perfect graph theorem, but Mirsky's theorem is easier to prove directly than Dilworth's theorem: if each element is labeled by the size of the largest chain in which it is maximal, then the subsets with equal labels form a partition into antichains, with the number of antichains equal to the size of the largest chain overall.{{r|mirsky-1971}} Every bipartite graph is a comparability graph. Thus, Kőnig's theorem can be seen as a special case of Dilworth's theorem, connected through the theory of perfect graphs.{{r|perfect-1980}}

[[File:Permutation graph.svg|thumb|The permutation graph of the permutation (4,3,5,1,2) connects pairs of elements whose ordering is reversed by the permutation.]]
A [[permutation graph]] is defined from a [[permutation]] on a totally ordered sequence of elements (conventionally, the integers from <math>1</math> to <math>n</math>), which form the vertices of the graph. The edges of a permutation graph connect pairs of elements whose ordering is reversed by the given permutation. These are naturally incomparability graphs, for a partial order in which <math>x\le y</math> whenever <math>x</math> occurs before <math>y</math> in both the given sequence and its permutation. The complement of a permutation graph is another permutation graph, for the reverse of the given permutation. Therefore, as well as being incomparability graphs, permutation graphs are comparability graphs. In fact, the permutation graphs are exactly the graphs that are both comparability and incomparability graphs.{{r|ple-1971}} A clique, in a permutation graph, is a subsequence of elements that appear in increasing order in the given permutation, and an independent set is a subsequence of elements that appear in decreasing order. In any perfect graph, the product of the clique number and independence number are at least the number of vertices; the special case of this inequality for permutation graphs is the [[Erdős–Szekeres theorem]].{{r|mirsky-1971}}

[[File:Interval graph.svg|thumb|upright=1.2|An [[interval graph]] and the intervals defining it]]
The [[interval graph]]s are the incomparability graphs of [[interval order]]s, orderings defined by sets of intervals on the real line with <math>x\le y</math> whenever interval <math>x</math> is completely to the left of interval <math>y</math>. In the corresponding interval graph, there is an edge from <math>x</math> to <math>y</math> whenever the two intervals have a point in common. Coloring these graphs can be used to model problems of assigning resources to tasks (such as classrooms to classes) with intervals describing the scheduled time of each task.{{r|klps-2007}} Both interval graphs and permutation graphs are generalized by the [[trapezoid graph]]s.{{r|dgp-1988}} Systems of intervals in which no two are nested produce a more restricted class of graphs, the [[indifference graph]]s, the incomparability graphs of [[semiorder]]s. These have been used to model human preferences under the assumption that, when items have utilities that are very close to each other, they will be incomparable.{{r|roberts-1969}} Intervals where every pair is nested or disjoint produce [[trivially perfect graph]]s,{{r|skrien-1982}} the comparability graphs of [[Tree (set theory)|ordered trees]]. In them, the independence number equals the number of [[maximal clique]]s.{{r|golumbic-1978}}