Download PDF - Cardinality of a minimal forbidden graph family for reducible additive hereditary graph propertiesAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Cardinality of a minimal forbidden graph family for reducible additive hereditary graph properties

Authors 1

Affiliations

  1. Faculty of Mathematics, Computer Science and Econometrics, University of Zielona Góra, Prof. Z. Szafrana 4a, 65-516 Zielona Góra, Poland

Abstract

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

Keywords

ENG
hereditary graph property, lattice of additive hereditary graph properties, minimal forbidden graph family, join in the lattice, reducibility

Bibliography

  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.
Discussiones Mathematicae Graph Theory
2009/29/2
Export to PBN, Opens in new tab
Pages:
263-274
Main language of publication
English
Received
2007-12-21
Accepted
2008-09-26
Published
2009

DOI: 10.7151/dmgt.1446

Exact and natural sciences