On hereditary properties of composition graphs
Vadim E. Levit, Eugen Mândrescu · Discussiones Mathematicae Graph Theory · 1998
The composition graph of a family of n+1 disjoint graphs fHi: 0 i ng is the graph H obtained by substituting the n vertices of H0 respectively by the graphs H1; H2;:::; Hn. If H has some hereditary property P, then necessarily all its factors enjoy the same property. For some sort of graphs it is sucient that all factors fHi: 0 i ng have a certain common P to endow H with this P. For instance, it is known that the composition graph of a family of perfect graphs is also a perfect graph (B. Bollobas, 1978), and the composition graph of a family of comparability graphs is a comparability graph as well (M.C. Golumbic, 1980). In this paper we show that the composition graph of a family of co-graphs (i.e., P4-free graphs), is also a co-graph, whereas for 1-perfect graphs (i.e., P4-free and C4-free graphs) and for threshold graphs (i.e., P4-free, C4-free and 2K2-free graphs), the corresponding factors fHi: 0 i ng have to be equipped with some special structure.