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 . 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.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1136,
author = {Amelie J. Berger},
title = {Minimal forbidden subgraphs of reducible graph properties},
journal = {Discussiones Mathematicae Graph Theory},
volume = {21},
year = {2001},
pages = {111-117},
zbl = {0989.05060},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1136}
}
Amelie J. Berger. Minimal forbidden subgraphs of reducible graph properties. Discussiones Mathematicae Graph Theory, Tome 21 (2001) pp. 111-117. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1136/
[000] [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. | Zbl 0902.05026
[001] [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. | Zbl 0151.33701
[002] [3] J. Nesetril and V. Rödl, Partitions of vertices, Comment Math. Universitatis Carolinae 17 (1) (1976) 85-95.