×

On hereditary properties of composition graphs. (English) Zbl 0935.05059

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.

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.)
PDFBibTeX XMLCite
Full Text: DOI Link