Editing Perfect graph (section)

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