Geodesic
Minimal forbidden subgraphs of reducible graph properties
Discussiones Mathematicae. Graph Theory, Tome 21 (2001) no. 1, pp. 111-117 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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.
Keywords: reducible graph properties, forbidden subgraphs, induced subgraphs 
@article{DMGT_2001_21_1_a7,
     author = {Berger, Amelie},
     title = {Minimal forbidden subgraphs of reducible graph properties},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {111--117},
     year = {2001},
     volume = {21},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2001_21_1_a7/}
}
TY  - JOUR
AU  - Berger, Amelie
TI  - Minimal forbidden subgraphs of reducible graph properties
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2001
SP  - 111
EP  - 117
VL  - 21
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DMGT_2001_21_1_a7/
LA  - en
ID  - DMGT_2001_21_1_a7
ER  - 
%0 Journal Article
%A Berger, Amelie
%T Minimal forbidden subgraphs of reducible graph properties
%J Discussiones Mathematicae. Graph Theory
%D 2001
%P 111-117
%V 21
%N 1
%U http://geodesic.mathdoc.fr/item/DMGT_2001_21_1_a7/
%G en
%F DMGT_2001_21_1_a7
Berger, Amelie. Minimal forbidden subgraphs of reducible graph properties. Discussiones Mathematicae. Graph Theory, Tome 21 (2001) no. 1, pp. 111-117. http://geodesic.mathdoc.fr/item/DMGT_2001_21_1_a7/

[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.