as the planar cographs) is closed under induced subgraph operations then it has a finite number of forbidden induced subgraphs. Computationally, this means that testing membership in such a subfamily may be performed in linear time, by using a bottom-up computation on the cotree of a given graph to test whether it contains any of these forbidden subgraphs. However, when the sizes of two cographs are both variable, testing whether one of them is an induced subgraph of the other is NP-complete. Cographs play a key role in algorithms for recognizing read-once functions. Enumeration The number of connected cographs with n vertices, for n = 1, 2, 3, ..., is: 1, 1, 2, 5, 12, 33, 90, 261, 766, 2312, 7068, 21965, 68954, ... For n > 1 there are the same number of disconnected cographs, because for every cograph exactly one of it or its complement graph is connected. Related graph families Subclasses Every complete graph is a cograph, with a cotree consisting of a single 1-node and leaves. Similarly, every complete bipartite graph is a cograph. Its cotree is rooted at a 1-node which has two 0-node children, one with leaf children and one with leaf children. A Turán graph may be formed by the join of a family of equal-sized independent sets; thus, it also is a cograph, with a cotree rooted at a 1-node that has a child 0-node for each independent set. Every threshold graph is also a cograph. A threshold graph may be formed by repeatedly adding one vertex, either connected to all previous vertices or to none of them; each such operation is one of the disjoint union or join operations by which a cotree may be formed. Superclasses The characterization of cographs by the property that every clique and maximal independent set have a nonempty intersection is a stronger version of the defining property of strongly perfect graphs, in which there every induced subgraph contains an independent set that intersects all maximal cliques. In a cograph, every maximal independent set intersects all maximal cliques. Thus, every cograph is strongly perfect. The fact that cographs are P4-free implies that they are perfectly orderable. In fact, every vertex order of a cograph is a perfect order which further implies that max clique finding and min colouring can be found in linear time with any greedy colouring and without the need for a cotree decomposition.