Czasopismo
Tytuł artykułu
Autorzy
Treść / Zawartość
Pełne teksty:
Warianty tytułu
Języki publikacji
Abstrakty
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.
Słowa kluczowe
Kategorie tematyczne
Wydawca
Czasopismo
Rocznik
Tom
Numer
Strony
111-117
Opis fizyczny
Daty
wydano
2001
otrzymano
2000-10-07
Twórcy
autor
- Department of Mathematics, Rand Afrikaans University, P.O. Box 524, Auckland Park, 2006 South Africa
Bibliografia
- [1] M. Borowiecki, I. Broere, M. Frick, P. Mihók and G. Semanišin, A survey of hereditary properties of graphs, Discuss. Math. Graph Theory 17 (1997) 5-50, doi: 10.7151/dmgt.1037.
- [2] P. Erdős and A. Hajnal, On chromatic number of graphs and set systems, Acta Math. Acad. Sci. Hungar. 17 (1966) 61-99, doi: 10.1007/BF02020444.
- [3] J. Nesetril and V. Rödl, Partitions of vertices, Comment Math. Universitatis Carolinae 17 (1) (1976) 85-95.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1136