- Tytuł:
- Minimal forbidden subgraphs of reducible graph properties
- Autorzy:
- Berger, Amelie
- Powiązania:
- https://bibliotekanauki.pl/articles/743439.pdf
- Data publikacji:
- 2001
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
reducible graph properties
forbidden subgraphs
induced subgraphs - Opis:
- A property of graphs is any class of graphs closed under isomorphism. Let ₁,₂,...,ₙ be properties of graphs. A graph G is (₁,₂,...,ₙ)-partitionable if the vertex set V(G) can be partitioned into n sets, {V₁,V₂,..., Vₙ}, such that for each i = 1,2,...,n, the graph $G[V_i] ∈ _i$. We write ₁∘₂∘...∘ₙ for the property of all graphs which have a (₁,₂,...,ₙ)-partition. An additive induced-hereditary property is called reducible if there exist additive induced-hereditary properties ₁ and ₂ such that = ₁∘₂. Otherwise is called irreducible. An additive induced-hereditary property can be defined by its minimal forbidden induced subgraphs: those graphs which are not in but which satisfy that every proper induced subgraph is in . We show that every reducible additive induced-hereditary property has infinitely many minimal forbidden induced subgraphs. This result is also seen to be true for reducible additive hereditary properties.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2001, 21, 1; 111-117
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł