Cardinality of a minimal forbidden graph family for reducible additive hereditary graph properties
Ewa Drgas-Burchardt
Discussiones Mathematicae Graph Theory, Tome 29 (2009), p. 263-274 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 2009-01-01
EUDML-ID : urn:eudml:doc:270353 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1446,
     author = {Ewa Drgas-Burchardt},
     title = {Cardinality of a minimal forbidden graph family for reducible additive hereditary graph properties},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {29},
     year = {2009},
     pages = {263-274},
     zbl = {1194.05132},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1446}
}

Ewa Drgas-Burchardt. Cardinality of a minimal forbidden graph family for reducible additive hereditary graph properties. Discussiones Mathematicae Graph Theory, Tome 29 (2009) pp. 263-274. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1446/

[000] [1] A.J. Berger, Minimal forbidden subgraphs of reducible graph properties, Discuss. Math. Graph Theory 21 (2001) 111-117, doi: 10.7151/dmgt.1136. | Zbl 0989.05060

[001] [2] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (North-Holland, New York, 1981). | Zbl 1226.05083

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

[003] [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. | Zbl 0902.05026

[004] [5] E.J. Cockayne, Colour classes for r-graphs, Canad. Math. Bull. 15 (1972) 349-354, doi: 10.4153/CMB-1972-063-2. | Zbl 0254.05106

[005] [6] E. Drgas-Burchardt, On uniqueness of a general factorization of graph properties, submitted.

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

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

[008] [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. | Zbl 0312.05128

[009] [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. | Zbl 0047.03402

[010] [11] J. Jakubik, On the Lattice of Additive Hereditary Properties of Finite Graphs, Discuss. Math. General Algebra and Applications 22 (2002) 73-86. | Zbl 1032.06003

[011] [12] M. Katchalski, W. McCuaig and S. Seager, Ordered colourings, Discrete Math. 142 (1995) 141-154, doi: 10.1016/0012-365X(93)E0216-Q.

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