Forbidden induced subgraph characterization of cograph contractions
Igor É. Zverovich, Inessa I. Zverovich · Journal of Graph Theory · 2004
Abstract Let S1, S2,…,St be pairwise disjoint non‐empty stable sets in a graph H. The graph H* is obtained from H by: (i) replacing each Si by a new vertex qi; (ii) joining each qi and qj, 1 ≤ i # j ≤ t, and; (iii) joining qi to all vertices in H – (S1 ∪ S2 ∪ ··· ∪ St) which were adjacent to some vertex of Si. A cograph is a P4‐free graph. A graph G is called a cograph contraction if there exist a cograph H and pairwise disjoint non‐empty stable sets in H for which G ≃ H*. Solving a problem proposed by Le [ 2 ], we give a finite forbidden induced subgraph characterization of cograph contractions. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 217–226, 2004