# On hereditary properties of composition graphs

Vadim E. Levit; Eugen Mandrescu

Discussiones Mathematicae Graph Theory (1998)

- Volume: 18, Issue: 2, page 183-195
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topVadim E. Levit, and Eugen Mandrescu. "On hereditary properties of composition graphs." Discussiones Mathematicae Graph Theory 18.2 (1998): 183-195. <http://eudml.org/doc/270387>.

@article{VadimE1998,

abstract = {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.},

author = {Vadim E. Levit, Eugen Mandrescu},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {composition graph; co-graphs; θ₁-perfect graphs; threshold graphs; composition; perfectness; comparability; permutation graph; factor graphs; composite graph},

language = {eng},

number = {2},

pages = {183-195},

title = {On hereditary properties of composition graphs},

url = {http://eudml.org/doc/270387},

volume = {18},

year = {1998},

}

TY - JOUR

AU - Vadim E. Levit

AU - Eugen Mandrescu

TI - On hereditary properties of composition graphs

JO - Discussiones Mathematicae Graph Theory

PY - 1998

VL - 18

IS - 2

SP - 183

EP - 195

AB - 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.

LA - eng

KW - composition graph; co-graphs; θ₁-perfect graphs; threshold graphs; composition; perfectness; comparability; permutation graph; factor graphs; composite graph

UR - http://eudml.org/doc/270387

ER -

## References

top- [1] B. Bollobás, Extremal graph theory (Academic Press, London, 1978). Zbl0419.05031
- [2] B. Bollobás and A.G. Thomason, Hereditary and monotone properties of graphs, in: R.L. Graham and J. Nešetřil, eds., The Mathematics of Paul Erdős, II, Algorithms and Combinatorics 14 (Springer-Verlag, 1997) 70-78. Zbl0866.05030
- [3] M. Borowiecki and P. Mihók, Hereditary properties of graphs, in: V.R. Kulli ed., Advances in Graph Theory (Vishwa Intern. Publication, Gulbarga,1991) 41-68.
- [4] M. Borowiecki, I. Broere, M. Frick, P. Mihók, G. Semanišin, A Survey of Hereditary Properties of Graphs, Discussiones Mathematicae Graph Theory 17 (1997) 5-50, doi: 10.7151/dmgt.1037. Zbl0902.05026
- [5] P. Borowiecki and J. Ivančo, P-bipartitions of minor hereditary properties, Discussiones Mathematicae Graph Theory 17 (1997) 89-93, doi: 10.7151/dmgt.1041. Zbl0914.05057
- [6] V. Chvátal and P.L. Hammer, Set-packing and threshold graphs, Res. Report CORR 73-21, University Waterloo, 1973.
- [7] S. Foldes and P.L. Hammer, Split graphs, in: F. Hoffman et al., eds., Proc. 8th Conf. on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, Louisiana, 1977) 311-315. Zbl0407.05071
- [8] M.C. Golumbic, Trivially perfect graphs, Discrete Math. 24 (1978) 105-107, doi: 10.1016/0012-365X(78)90178-4.
- [9] M.C. Golumbic, Algorithmic graph theory and perfect graphs (Academic Press, London, 1980).
- [10] J.L. Jolivet, Sur le joint d' une famille de graphes, Discrete Math. 5 (1973) 145-158, doi: 10.1016/0012-365X(73)90106-4. Zbl0256.05124
- [11] N.V.R. Mahadev and U.N. Peled, Threshold graphs and related topics (North-Holland, Amsterdam, 1995). Zbl0852.05001
- [12] E. Mandrescu, Triangulated graph products, Anal. Univ. Galatzi (1991) 37-44.
- [13] K.R. Parthasarathy, S.A. Choudum and G. Ravindra, Line-clique cover number of a graph, Proc. Indian Nat. Sci. Acad., Part A 41 (3) (1975) 281-293. Zbl0335.05127
- [14] U.N. Peled, Matroidal graphs, Discrete Math. 20 (1977) 263-286.
- [15] A. Pnueli, A. Lempel and S. Even, Transitive orientation of graphs and identification of permutation graphs, Canad. J. Math. 23 (1971) 160-175, doi: 10.4153/CJM-1971-016-5. Zbl0204.24604
- [16] G. Ravindra and K.R. Parthasarathy, Perfect Product Graphs, Discrete Math. 20 (1977) 177-186, doi: 10.1016/0012-365X(77)90056-5. Zbl0371.05028
- [17] G. Sabidussi, The composition of graphs, Duke Math. J. 26 (1959) 693-698, doi: 10.1215/S0012-7094-59-02667-5. Zbl0095.37802

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.