Levit, Vadim E.; Mandrescu, Eugen On hereditary properties of composition graphs. (English) Zbl 0935.05059 Discuss. Math., Graph Theory 18, No. 2, 183-195 (1998). Let \(H_0= (V_0,E_0)\) be a graph with vertex set \(V_0= \{v_1,v_2,\dots, v_n\}\) of \(n\) elements and \(H_i= (V_i,E_i)\), \(1\leq i\leq n\), be \(n\) disjoint graphs. Then their composition graph \(H\) has vertex set \(V= \bigcup\{V_i\mid 1\leq i\leq n\}\) and edge set \(E= \bigcup\{E_i\mid 1\leq i\leq n\}\cup \{xy\mid x\in V_i, y\in V_j, v_iv_j\in E_0, 1\leq i, j\leq n\}\). If \(P\) is a hereditary property for graphs, it is clear that if the composition \(H\) has property \(P\), then each of the factors \(H_i\), \(0\leq i\leq n\), has also the property \(P\). It is known that the converse is also true in some cases, as e.g. perfectness and comparability.In this paper the authors prove that the composition of a family of graphs is a permutation graph or a co-graph (i.e. a \(P_4\)-free graph) if and only if each of its factors is also a permutation graph (respectively, a co-graph). For \(\Theta_1\)-perfect graphs (those which do not have an induced \(P_4\) or \(C_4\)) and threshold graphs (those that do not have an induced \(P_4\), \(C_4\) or \(2K_2\)), the factor graphs should satisfy some extra conditions besides being \(\Theta_1\)-perfect (respectively, threshold) in order that the composite graph has this property. These conditions are a bit too long to be mentioned here. Reviewer: K.R.Parthasarathy (Narayanapuram) MSC: 05C38 Paths and cycles 05C75 Structural characterization of families of graphs 05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) Keywords:composition; perfectness; comparability; permutation graph; threshold graphs; factor graphs; composite graph PDFBibTeX XMLCite \textit{V. E. Levit} and \textit{E. Mandrescu}, Discuss. Math., Graph Theory 18, No. 2, 183--195 (1998; Zbl 0935.05059) Full Text: DOI Link