self-complementary graph is a graph that is isomorphic to its own complement. Examples include the four-vertex path graph and five-vertex cycle graph. There is no known characterization of self-complementary graphs. Several classes of graphs are self-complementary, in the sense that the complement of any graph in one of these classes is another graph in the same class. Perfect graphs are the graphs in which, for every induced subgraph, the chromatic number equals the size of the maximum clique. The fact that the complement of a perfect graph is also perfect is the perfect graph theorem of László Lovász. Cographs are defined as the graphs that can be built up from single vertices by disjoint union and complementation operations. They form a self-complementary family of graphs: the complement of any cograph is another different cograph. For cographs of more than one vertex, exactly one graph in each complementary pair is connected, and one equivalent definition of cographs is that each of their connected induced subgraphs has a disconnected complement. Another, self-complementary definition is that they are the graphs with no induced subgraph in the form of a four-vertex path. Another self-complementary class of graphs is the class of split graphs, the graphs in which the vertices can be partitioned into a clique and an independent set. The same partition gives an independent set and a clique in the complement graph. The threshold graphs are the graphs formed by repeatedly adding either an independent vertex (one with no neighbors) or a universal vertex (adjacent to all previously-added vertices). These two operations are complementary and they generate a self-complementary class of graphs. Algorithmic aspects In the analysis of algorithms on graphs, the distinction between a graph and its complement is an important one, because a sparse graph (one with a small number of edges compared to the number of pairs of vertices) will in general not have a sparse complement, and so an algorithm that takes time proportional to the number of edges on a given graph may take a much larger amount of time if the same algorithm is run on an explicit representation of the complement graph. Therefore, researchers have studied algorithms that perform standard graph computations on the complement of an input graph, using an implicit graph representation that does not require the explicit construction of the complement graph. In particular, it is possible to simulate either depth-first search or