×

A good characterization of cograph contractions. (English) Zbl 0922.05045

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.

MSC:

05C75 Structural characterization of families of graphs
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] and (Editors), Topics on perfect graphs, Annals Discrete Math 21, North-Holland, Amsterdam, 1984. · Zbl 0546.00006
[2] Corneil, Discrete Appl Math 10 pp 163– (1981)
[3] Davis, J ACM 7 pp 201– (1960)
[4] Even, SIAM J Comput 5 pp 691– (1976)
[5] Algorithmic graph theory and perfect graphs, Academic New York, 1980. · Zbl 0541.05054
[6] Hayward, J Combin Theory (B) 39 pp 200– (1985)
[7] and On P4-transversals of perfect graphs, to appear.
[8] Hujter, Combin Prob Comput 5 pp 35– (1996) · Zbl 0846.05034 · doi:10.1017/S0963548300001826
[9] Jung, J Combin Theory (B) 24 pp 125– (1978)
[10] Seinsche, J Combin Theory (B) 16 pp 191– (1974)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.