PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2001 | 21 | 1 | 111-117
Tytuł artykułu

Minimal forbidden subgraphs of reducible graph properties

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Wydawca
Rocznik
Tom
21
Numer
1
Strony
111-117
Opis fizyczny
Daty
wydano
2001
otrzymano
2000-10-07
Twórcy
  • 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
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.