Geodesic
Cardinality of a minimal forbidden graph family for reducible additive hereditary graph properties
Discussiones Mathematicae. Graph Theory, Tome 29 (2009) no. 2, pp. 263-274.

Voir la notice de l'article provenant de la source Library of Science

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 
@article{DMGT_2009_29_2_a4,
     author = {Drgas-Burchardt, Ewa},
     title = {Cardinality of a minimal forbidden graph family for reducible additive hereditary graph properties},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {263--274},
     publisher = {mathdoc},
     volume = {29},
     number = {2},
     year = {2009},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2009_29_2_a4/}
}
TY  - JOUR
AU  - Drgas-Burchardt, Ewa
TI  - Cardinality of a minimal forbidden graph family for reducible additive hereditary graph properties
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2009
SP  - 263
EP  - 274
VL  - 29
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2009_29_2_a4/
LA  - en
ID  - DMGT_2009_29_2_a4
ER  - 
%0 Journal Article
%A Drgas-Burchardt, Ewa
%T Cardinality of a minimal forbidden graph family for reducible additive hereditary graph properties
%J Discussiones Mathematicae. Graph Theory
%D 2009
%P 263-274
%V 29
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2009_29_2_a4/
%G en
%F DMGT_2009_29_2_a4
Drgas-Burchardt, Ewa. Cardinality of a minimal forbidden graph family for reducible additive hereditary graph properties. Discussiones Mathematicae. Graph Theory, Tome 29 (2009) no. 2, pp. 263-274. http://geodesic.mathdoc.fr/item/DMGT_2009_29_2_a4/

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