On hereditary properties of composition graphs

Paths and cycles (05C38) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Structural characterization of families of graphs (05C75)

Review text

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.

Recommendations

Cited in

(7)

This page was built for publication: On hereditary properties of composition graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4254302)