Minimal reducible bounds for hom-properties of graphs
Amelie Berger ; Izak Broere
Discussiones Mathematicae Graph Theory, Tome 19 (1999), p. 143-158 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

Let H be a fixed finite graph and let → H be a hom-property, i.e. the set of all graphs admitting a homomorphism into H. We extend the definition of → H to include certain infinite graphs H and then describe the minimal reducible bounds for → H in the lattice of additive hereditary properties and in the lattice of hereditary properties.

Publié le : 1999-01-01
EUDML-ID : urn:eudml:doc:270586 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1091,
     author = {Amelie Berger and Izak Broere},
     title = {Minimal reducible bounds for hom-properties of graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {19},
     year = {1999},
     pages = {143-158},
     zbl = {0958.05051},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1091}
}

Amelie Berger; Izak Broere. Minimal reducible bounds for hom-properties of graphs. Discussiones Mathematicae Graph Theory, Tome 19 (1999) pp. 143-158. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1091/

[000] [1] M. Borowiecki, I. Broere, M. Frick, P. Mihók and G. Semanišin, A survey of Hereditary Properties of Graphs, Discussiones Mathematicae Graph Theory 17 (1997) 5-50, doi: 10.7151/dmgt.1037. | Zbl 0902.05026

[001] [2] P. Hell and J. Nesetril, The core of a graph, Discrete Math. 109 (1992) 117-126, doi: 10.1016/0012-365X(92)90282-K. | Zbl 0803.68080

[002] [3] J. Kratochví l and P. Mihók, Hom properties are uniquely factorisable into irreducible factors, to appear in Discrete Math.

[003] [4] J. Kratochví l, P. Mihók and G. Semanišin, Graphs maximal with respect to hom-properties, Discussiones Mathematicae Graph Theory 17 (1997) 77-88, doi: 10.7151/dmgt.1040. | Zbl 0905.05038

[004] [5] J. Nesetril, Graph homomorphisms and their structure, in: Y. Alavi and A. Schwenk, eds., Graph Theory, Combinatorics and Applications: Proceedings of the Seventh Quadrennial International Conference on the Theory and Applications of Graphs 2 (1995) 825-832. | Zbl 0858.05049

[005] [6] J. Nesetril, V. Rödl, Partitions of Vertices, Comment. Math. Univ. Carolin. 17 (1976) 675-681.