Minimal forbidden subgraphs of reducible graph properties
Amelie Berger · Discussiones Mathematicae Graph Theory · 2001
A property of graphs is any class of graphs closed under isomorphism.Let P 1 , P 2 , . . .,for the property of all graphs which have a (P 1 , P 2 , . . ., P n )-partition.An additive inducedhereditary property R is called reducible if there exist additive inducedhereditary properties P 1 and P 2 such that R = P 1 •P 2 .Otherwise R is called irreducible.An additive induced-hereditary property P can be defined by its minimal forbidden induced subgraphs: those graphs which are not in P but which satisfy that every proper induced subgraph is in P. We show that every reducible additive inducedhereditary property has infinitely many minimal forbidden induced subgraphs.This result is also seen to be true for reducible additive hereditary properties.