- Tytuł:
- On hereditary properties of composition graphs
- Autorzy:
-
Levit, Vadim
Mandrescu, Eugen - Powiązania:
- https://bibliotekanauki.pl/articles/744221.pdf
- Data publikacji:
- 1998
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
composition graph
co-graphs
θ₁-perfect graphs
threshold graphs - Opis:
- 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 1998, 18, 2; 183-195
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł