A good characterization of cograph contractions (Q4238044)

All graphs considered in the present paper are finite, undirected and simple ones. Such graphs \(H\) with no induced path on four vertices are called complement-reducible graphs or cographs. A graph \(G\) is defined to be a cograph contraction if it is obtained from a cograph \(H\) by contracting some pairwise disjoint independent sets and then making the contracted vertices pairwise adjacent. For this new graph \(H^*\) we have \(G= H^*\). M. Hujter and Zs. Tuza proved that cograph contractions are perfect, and they posed the characterization problem of cograph contractions which is solved by the present article. In Section 2 two necessary conditions for cograph contractions are proved, namely: (1) each induced \(P_4\) in \(G\) has at least one midpoint in a clique \(Q\) in \(H^*\) (\(P_4\)-condition); (2) each induced \(\overline P_5\) in \(G\) has both midpoints in a clique \(Q\) in \(H^*\) (\(\overline P_5\)-condition). These conditions imply that cograph contractions are weakly triangulated graphs, that means, graphs without induced \(C_\ell\) and \(\overline C_\ell\) \((\ell\geq 5)\). In Section 3 the main result of this paper is given by Theorem 3.1: A graph \(G\) is a cograph contraction iff it has a clique satisfying the \(P_4\)-condition and the \(\overline P_5\)-condition. This characterization yields a polynomial recognition algorithm for cograph contractions, by which the author gets a ``good'' clique in \(G\). Therefore the proof of Theorem 3.1 is a constructive one. This is described in detail and Sections 4 and 5. The construction shows that, in most cases, cograph contractions are obtained from a disconnected cograph \(H\). Therefore, the author also investigates the case of a connected cograph \(H\). Section 6 contains the following result: A graph \(G\) is a connected-cograph contraction iff it is the join of two cograph contractions (Theorem 6.1). Moreover, an open problem is formulated.