Editing Perfect graph (section)

==Families of graphs==
Many well-studied families of graphs are perfect,{{r|hougardy-2006}} and in many cases the fact that these graphs are perfect corresponds to a [[minimax theorem]] for some kinds of combinatorial structure defined by these graphs. Examples of this phenomenon include the perfection of [[bipartite graph]]s and their [[line graph]]s, associated with [[Kőnig's theorem (graph theory)|Kőnig's theorem]] relating [[maximum matching]]s and [[vertex cover]]s in bipartite graphs, and the perfection of [[comparability graph]]s, associated with [[Dilworth's theorem]] and [[Mirsky's theorem]] on [[Chain (order theory)|chains]] and [[antichain]]s in [[partially ordered set]]s. Other important classes of graphs, defined by having a structure related to the holes and antiholes of the strong perfect graph theorem, include the [[chordal graph]]s, [[Meyniel graph]]s, and their subclasses.

===Bipartite graphs and line graphs===
[[File:Bipartite line graph.svg|thumb|upright=1.35|A bipartite graph (left) and its line graph (right). The shaded cliques in the line graph correspond to the vertices of the underlying bipartite graph, and have size equal to the degree of the corresponding vertex.]]
In [[bipartite graph]]s (with at least one edge) the chromatic number and clique number both equal two. Their induced subgraphs remain bipartite, so bipartite graphs are perfect.{{r|hougardy-2006}} Other important families of graphs are bipartite, and therefore also perfect, including for instance the [[Tree (graph theory)|trees]] and [[median graph]]s.{{r|bipartite}} By the perfect graph theorem, maximum independent sets in bipartite graphs have the same size as their minimum clique covers. The maximum independent set is complementary to a minimum [[vertex cover]], a set of vertices that touches all edges. A minimum clique cover consists of a [[maximum matching]] (as many disjoint edges as possible) together with one-vertex cliques for all remaining vertices, and its size is the number of vertices minus the number of matching edges. Therefore, this equality can be expressed equivalently as an equality between the size of the maximum matching and the minimum vertex cover in bipartite graphs, the usual formulation of [[Kőnig's theorem (graph theory)|Kőnig's theorem]].{{r|konig-1931|trotter-1977}}

A matching, in any graph <math>G</math>, is the same thing as an independent set in the [[line graph]] <math>L(G)</math>, a graph that has a vertex for each edge in <math>G</math> and an edge between two vertices in <math>L(G)</math> for each pair of edges in <math>G</math> that share an endpoint. Line graphs have two kinds of cliques: sets of edges in <math>G</math> with a common endpoint, and triangles in <math>G</math>. In bipartite graphs, there are no triangles, so a clique cover in <math>L(G)</math> corresponds to a vertex cover in <math>G</math>. Therefore, in line graphs of bipartite graphs, the independence number and clique cover number are equal. Induced subgraphs of line graphs of bipartite graphs are line graphs of subgraphs, so the line graphs of bipartite graphs are perfect.{{r|trotter-1977}} Examples include the [[rook's graph]]s, the line graphs of [[complete bipartite graph]]s. Every line graph of a bipartite graph is an induced subgraph of a rook's graph.{{r|bg-2006}}

Because line graphs of bipartite graphs are perfect, their clique number equals their chromatic number. The clique number of the line graph of a bipartite graph is the [[degree (graph theory)|maximum degree]] of any vertex of the underlying bipartite graph. The chromatic number of the line graph of a bipartite graph is the [[chromatic index]] of the underlying bipartite graph, the minimum number of colors needed to color the edges so that touching edges have different colors. Each color class forms a matching, and the chromatic index is the minimum number of matchings needed to cover all edges. The equality of maximum degree and chromatic index, in bipartite graphs, is another theorem of [[Dénes Kőnig]].{{r|konig-1916}} In arbitrary simple graphs, they can differ by one; this is [[Vizing's theorem]].{{r|trotter-1977}}

[[File:Line perfect graph.svg|thumb|A [[line perfect graph]], with black bipartite biconnected components, blue <math>K_4</math>, and red triangular books]]
The underlying graph <math>G</math> of a perfect line graph <math>L(G)</math> is a [[line perfect graph]]. These are the graphs whose [[biconnected component]]s are  bipartite graphs, the [[complete graph]] <math>K_4</math>, and [[Book (graph theory)|triangular books]], sets of triangles sharing an edge. These components are perfect, and their combination preserves perfection, so every line perfect graph is perfect.{{r|trotter-1977}}

The bipartite graphs, their complements, and the line graphs of bipartite graphs and their complements form four basic classes of perfect graphs that play a key role in the proof of the strong perfect graph theorem. According to the structural decomposition of perfect graphs used as part of this proof, every perfect graph that is not already in one of these four classes can be decomposed by partitioning its vertices into subsets, in one of four ways, called a 2-join, the complement of a 2-join, a homogeneous pair, or a [[skew partition]].{{r|cornuejols-2002}}

===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}}

===Split graphs and random perfect graphs===
[[File:Colored split graph.svg|thumb|upright|Optimal coloring of a [[split graph]], obtained by giving each vertex of a maximal clique (heavy vertices and edges) a separate color, and then giving each remaining vertex the same color as a clique vertex to which it is not adjacent]]
A [[split graph]] is a graph that can be partitioned into a clique and an independent set. It can be colored by assigning a separate color to each vertex of a maximal clique, and then coloring each remaining vertex the same as a non-adjacent clique vertex. Therefore, these graphs have equal clique numbers and chromatic numbers, and are perfect.{{r|splittance}} A broader class of graphs, the ''unipolar graphs'' can be partitioned into a clique and a [[cluster graph]], a disjoint union of cliques. These include also the bipartite graphs, for which the cluster graph is just a single clique. The unipolar graphs and their complements together form the class of ''generalized split graphs''. [[Almost all]] perfect graphs are generalized split graphs, in the sense that the fraction of perfect <math>n</math>-vertex graphs that are generalized split graphs goes to one in the limit as <math>n</math> grows arbitrarily large.{{r|ps-1992}}

Other limiting properties of almost all perfect graphs can be determined by studying the generalized split graphs. In this way, it has been shown that almost all perfect graphs contain a [[Hamiltonian cycle]]. If <math>H</math> is an arbitrary graph, the limiting probability that <math>H</math> occurs as an induced subgraph of a large random perfect graph is 0, 1/2, or 1, respectively as <math>H</math> is not a generalized split graph, is unipolar or co-unipolar but not both, or is both unipolar and co-unipolar.{{r|my-2019}}

===Incremental constructions===
Several families of perfect graphs can be characterized by an incremental construction in which the graphs in the family are built up by adding one vertex at a time, according to certain rules, which guarantee that after each vertex is added the graph remains perfect.
* The [[chordal graph]]s are the graphs formed by a construction of this type in which, at the time a vertex is added, its neighbors form a clique. Chordal graphs may also be characterized as the graphs that have no holes (even or odd).{{r|rose}} They include as special cases the forests, the interval graphs,{{r|dirac}} and the [[maximal outerplanar graph]]s.{{r|harary-74}} The split graphs are exactly the graphs that are chordal and have a chordal complement.{{r|fh77}} The [[K-tree|{{mvar|k}}-trees]], central to the definition of [[treewidth]], are chordal graphs formed by starting with a {{math|(''k'' + 1)}}-vertex clique and repeatedly adding a vertex so that it and its neighbors form a clique of the same size.{{r|rose}}
[[File:Distance-hereditary construction.svg|thumb|Three types of vertex addition in a [[distance-hereditary graph]]]]
* The [[distance-hereditary graph]]s are formed, starting from a single-vertex graph, by repeatedly adding degree-one vertices ("pendant vertices") or copies of existing vertices (with the same neighbors). Each vertex and its copy may be adjacent (''true twins'') or non-adjacent (''false twins''). In every connected induced subgraph of these graphs, the distances between vertices are the same as in the whole graph. If only the twin operations are used, the result is a [[cograph]].{{r|bm-1986}} The cographs are the comparability graphs of [[series-parallel partial order]]s{{r|jung-1978}} and can also be formed by a different construction process combining complementation and the [[disjoint union of graphs]].{{r|clsb-1981}}
* The graphs that are both chordal and distance-hereditary are called [[Ptolemaic graph]]s, because their distances obey [[Ptolemy's inequality]].{{r|kc-1965}} They have a restricted form of the distance-hereditary construction sequence, in which a false twin can only be added when its neighbors would form a clique.{{r|bm-1986}} They include as special cases the [[windmill graph]]s consisting of cliques joined at a single vertex, and the [[block graph]]s in which each biconnected component is a clique.{{r|kc-1965}}
* The [[threshold graph]]s are formed from an empty graph by repeatedly adding either an [[isolated vertex]] (connected to nothing else) or a [[universal vertex]] (connected to all other vertices).{{r|hk-2007}} They are special cases of the split graphs and the trivially perfect graphs. They are exactly the graphs that are both trivially perfect and the complement of a trivially perfect graph; they are also exactly the graphs that are both cographs and split graphs.{{r|threshold}}

If the vertices of a chordal graph are colored in the order of an incremental construction sequence using a [[greedy coloring]] algorithm, the result will be an optimal coloring. The reverse of the vertex ordering used in this construction is called an ''elimination order''.{{r|gavril-1972}} Similarly, if the vertices of a distance-hereditary graph are colored in the order of an incremental construction sequence, the resulting coloring will be optimal.{{r|hm90}} If the vertices of a comparability graph are colored in the order of a [[linear extension]] of its underlying partial order, the resulting coloring will be optimal. This property is generalized in the family of [[perfectly orderable graph]]s, the graphs for which there exists an ordering that, when restricted to any induced subgraph, causes greedy coloring to be optimal.{{r|hr89}} The cographs are exactly the graphs for which all vertex orderings have this property.{{r|gl88}} Another subclass of perfectly orderable graphs are the complements of [[tolerance graph]]s, a generalization of interval graphs.{{r|gt-2004}}

===Strong perfection===
The [[strongly perfect graph]]s are graphs in which, in every induced subgraph, there exists an independent set that intersects all [[maximal clique]]s. In the [[Meyniel graph]]s or ''very strongly perfect graphs'', every vertex belongs to such an independent set. The Meyniel graphs can also be characterized as the graphs in which every odd cycle of length five or more has at least two chords.{{r|hoang-1987}}

[[File:Cubic matchstick graph.svg|thumb|upright|A [[parity graph]] that is neither [[Distance-hereditary graph|distance-hereditary]] nor [[Bipartite graph|bipartite]]]]
A [[parity graph]] is defined by the property that between every two vertices, all [[induced path]]s have equal parity: either they are all even in length, or they are all odd in length. These include the distance-hereditary graphs, in which all induced paths between two vertices have the same length,{{r|cd-1999}} and bipartite graphs, for which all paths (not just induced paths) between any two vertices have equal parity. Parity graphs are Meyniel graphs, and therefore perfect: if a long odd cycle had only one chord, the two parts of the cycle between the endpoints of the chord would be induced paths of different parity. The prism over any parity graph (its [[Cartesian product of graphs|Cartesian product]] with a single edge) is another parity graph, and the parity graphs are the only graphs whose prisms are perfect.{{r|jansen-1998}}