# Minimal forbidden subgraphs of reducible graph properties

Discussiones Mathematicae Graph Theory (2001)

- Volume: 21, Issue: 1, page 111-117
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topAmelie 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 -

## References

top- [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. Zbl0902.05026
- [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. Zbl0151.33701
- [3] J. Nesetril and V. Rödl, Partitions of vertices, Comment Math. Universitatis Carolinae 17 (1) (1976) 85-95.

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.