DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 21(1) (2001) 111-117
DOI: 10.7151/dmgt.1136

MINIMAL FORBIDDEN SUBGRAPHS OF REDUCIBLE GRAPH PROPERTIES

Amelie J. Berger

Department of Mathematics
Rand Afrikaans University
P.O. Box 524, Auckland Park, 2006 South Africa

e-mail: abe@raua.rau.ac.za

Abstract

A property of graphs is any class of graphs closed under isomorphism. Let P1, P2, …,Pn be properties of graphs. A graph G is (P1, P2, …,Pn)-partitionable if the vertex set V(G) can be partitioned into n sets, { V1, V2, …, Vn}, such that for each i = 1,2,...,n, the graph G[Vi] ∈ Pi. We write P1 ºP2 º… ºPn for the property of all graphs which have a (P1, P2, …,Pn)-partition. An additive induced-hereditary property ℜ is called reducible if there exist additive induced-hereditary properties P1 and P2 such that ℜ = P1ºP2. Otherwise ℜ 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 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.

2000 Mathematics Subject Classification: 05C55, 05C15.

References

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

Received 7 October 2000