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

Discussiones Mathematicae Graph Theory (2009)

- Volume: 29, Issue: 2, page 263-274
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topEwa Drgas-Burchardt. "Cardinality of a minimal forbidden graph family for reducible additive hereditary graph properties." Discussiones Mathematicae Graph Theory 29.2 (2009): 263-274. <http://eudml.org/doc/270353>.

@article{EwaDrgas2009,

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.},

author = {Ewa Drgas-Burchardt},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {hereditary graph property; lattice of additive hereditary graph properties; minimal forbidden graph family; join in the lattice; reducibility},

language = {eng},

number = {2},

pages = {263-274},

title = {Cardinality of a minimal forbidden graph family for reducible additive hereditary graph properties},

url = {http://eudml.org/doc/270353},

volume = {29},

year = {2009},

}

TY - JOUR

AU - Ewa Drgas-Burchardt

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

JO - Discussiones Mathematicae Graph Theory

PY - 2009

VL - 29

IS - 2

SP - 263

EP - 274

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

LA - eng

KW - hereditary graph property; lattice of additive hereditary graph properties; minimal forbidden graph family; join in the lattice; reducibility

UR - http://eudml.org/doc/270353

ER -

## References

top- [1] A.J. Berger, Minimal forbidden subgraphs of reducible graph properties, Discuss. Math. Graph Theory 21 (2001) 111-117, doi: 10.7151/dmgt.1136. Zbl0989.05060
- [2] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (North-Holland, New York, 1981). Zbl1226.05083
- [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. Zbl0902.05026
- [5] E.J. Cockayne, Colour classes for r-graphs, Canad. Math. Bull. 15 (1972) 349-354, doi: 10.4153/CMB-1972-063-2. Zbl0254.05106
- [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. Zbl0312.05128
- [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. Zbl0047.03402
- [11] J. Jakubik, On the Lattice of Additive Hereditary Properties of Finite Graphs, Discuss. Math. General Algebra and Applications 22 (2002) 73-86. Zbl1032.06003
- [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.

## NotesEmbed ?

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