Editing Perfect graph (section)

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