PDF

Discussiones Mathematicae Graph Theory 29(2) (2009) 263-274
DOI: https://doi.org/10.7151/dmgt.1446

CARDINALITY OF A MINIMAL FORBIDDEN GRAPH FAMILY FOR REDUCIBLE ADDITIVE HEREDITARY GRAPH PROPERTIES

Ewa Drgas-Burchardt

Faculty of Mathematics, Computer Science and Econometrics
University of Zielona Góra
Prof. Z. Szafrana 4a, 65-516 Zielona Góra, Poland
e-mail: E.Drgas-Burchardt@wmie.uz.zgora.pl

Abstract

An additive hereditary graph property is any class of simple graphs, which is closed under isomorphisms unions and taking subgraphs. Let L^a denote a class of all such properties. In the paper, we consider H-reducible over L^a properties with H being a fixed graph. The finiteness of the sets of all minimal forbidden graphs is analyzed for such properties.

Keywords: hereditary graph property, lattice of additive hereditary graph properties, minimal forbidden graph family, join in the lattice, reducibility.

2000 Mathematics Subject Classification: 05C75, 05C15, 05C35.

References

[1]	A.J. Berger, Minimal forbidden subgraphs of reducible graph properties, Discuss. Math. Graph Theory 21 (2001) 111-117, doi: 10.7151/dmgt.1136.
[2]	J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (North-Holland, New York, 1981).
[3]	M. Borowiecki and P. Mihók, Hereditary properties of graphs, in: V.R. Kulli, ed., Advances in Graph Theory (Vishawa International Publication, Gulbarga, 1991) 41-68.
[4]	M. Borowiecki, I. Broere, M. Frick, P.Mihók and G. Semanišin, Survey of hereditary properties of graphs, Discuss. Math. Graph Theory 17 (1997) 5-50, doi: 10.7151/dmgt.1037.
[5]	E.J. Cockayne, Colour classes for r-graphs, Canad. Math. Bull. 15 (1972) 349-354, doi: 10.4153/CMB-1972-063-2.
[6]	E. Drgas-Burchardt, On uniqueness of a general factorization of graph properties, submitted.
[7]	E. Drgas-Burchardt, A note on joins of additive hereditary graph properties, Discuss. Math. Graph Theory 26 (2006) 413-418, doi: 10.7151/dmgt.1333.
[8]	M. Frick, A survey of (m,k)-colorings, in: J. Gimbel et al. (Eds), Quo Vadis Graph Theory? A source book for challenges and directions, Annals Discrete Math. 55 (North-Holland, Amsterdam, 1993) 45-57, doi: 10.1016/S0167-5060(08)70374-1.
[9]	D.L. Greenwell, R.L. Hemminger and J. Klerlein, Forbidden subgraphs, in: Proceedings of the 4th S-E Conf. Combinatorics, Graph Theory and Computing (Utilitas Math., Winnipeg, Man., 1973) 389-394.
[10]	G. Higman, Ordering by divisibility in abstract algebras, Proc. London Math. Soc. 2 (1952) 326-336, doi: 10.1112/plms/s3-2.1.326.
[11]	J. Jakubik, On the Lattice of Additive Hereditary Properties of Finite Graphs, Discuss. Math. General Algebra and Applications 22 (2002) 73-86.
[12]	M. Katchalski, W. McCuaig and S. Seager, Ordered colourings, Discrete Math. 142 (1995) 141-154, doi: 10.1016/0012-365X(93)E0216-Q.
[13]	N. Robertson and P.D. Seymour, Graph minors - a survey, in: Surveys in Combinatorics 1985 (Glasgow, 1985), London Math. Soc. Lecture Note Ser. 103 (Cambridge University Press., Cambridge 1985), 153-171.

Received 21 December 2007
Revised 26 September 2008
Accepted 1 December 2008