Geodesic
On hereditary properties of composition graphs
Discussiones Mathematicae. Graph Theory, Tome 18 (1998) no. 2, pp. 183-195

Voir la notice de l'article provenant de la source Library of Science

The composition graph of a family of n+1 disjoint graphs H_i:0 ≤ i ≤ n is the graph H obtained by substituting the n vertices of H₀ respectively by the graphs H₁,H₂,...,Hₙ. If H has some hereditary property P, then necessarily all its factors enjoy the same property. For some sort of graphs it is sufficient that all factors H_i: 0 ≤ i ≤ n 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., P₄-free graphs), is also a co-graph, whereas for θ₁-perfect graphs (i.e., P₄-free and C₄-free graphs) and for threshold graphs (i.e., P₄-free, C₄-free and 2K₂-free graphs), the corresponding factors H_i:0 ≤ i ≤ n have to be equipped with some special structure.
Keywords: composition graph, co-graphs, θ₁-perfect graphs, threshold graphs 
@article{DMGT_1998_18_2_a4,
     author = {Levit, Vadim and Mandrescu, Eugen},
     title = {On hereditary properties of composition graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {183--195},
     publisher = {mathdoc},
     volume = {18},
     number = {2},
     year = {1998},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_1998_18_2_a4/}
}
TY  - JOUR
AU  - Levit, Vadim
AU  - Mandrescu, Eugen
TI  - On hereditary properties of composition graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 1998
SP  - 183
EP  - 195
VL  - 18
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_1998_18_2_a4/
LA  - en
ID  - DMGT_1998_18_2_a4
ER  - 
%0 Journal Article
%A Levit, Vadim
%A Mandrescu, Eugen
%T On hereditary properties of composition graphs
%J Discussiones Mathematicae. Graph Theory
%D 1998
%P 183-195
%V 18
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_1998_18_2_a4/
%G en
%F DMGT_1998_18_2_a4
Levit, Vadim; Mandrescu, Eugen. On hereditary properties of composition graphs. Discussiones Mathematicae. Graph Theory, Tome 18 (1998) no. 2, pp. 183-195. http://geodesic.mathdoc.fr/item/DMGT_1998_18_2_a4/