Minimal forbidden subgraphs of reducible graph properties

Amelie J. Berger. "Minimal forbidden subgraphs of reducible graph properties." Discussiones Mathematicae Graph Theory 21.1 (2001): 111-117. <http://eudml.org/doc/270261>.

@article{AmelieJ2001,
abstract = {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.},
author = {Amelie J. Berger},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {reducible graph properties; forbidden subgraphs; induced subgraphs; forbidden induced subgraphs; hereditary properties},
language = {eng},
number = {1},
pages = {111-117},
title = {Minimal forbidden subgraphs of reducible graph properties},
url = {http://eudml.org/doc/270261},
volume = {21},
year = {2001},
}

TY - JOUR
AU - Amelie J. Berger
TI - Minimal forbidden subgraphs of reducible graph properties
JO - Discussiones Mathematicae Graph Theory
PY - 2001
VL - 21
IS - 1
SP - 111
EP - 117
AB - 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.
LA - eng
KW - reducible graph properties; forbidden subgraphs; induced subgraphs; forbidden induced subgraphs; hereditary properties
UR - http://eudml.org/doc/270261
ER -