PDF

Discussiones Mathematicae Graph Theory 19(2) (1999) 143-158
DOI: https://doi.org/10.7151/dmgt.1091

MINIMAL REDUCIBLE BOUNDS FOR HOM-PROPERTIES OF GRAPHS

Amelie Berger and Izak Broere

Department of Mathematics
Rand Afrikaans University
P.O. Box 524, Auckland Park
2006 South Africa
e-mail: abe@raua.rau.ac.za
e-mail: ib@na.rau.ac.za

Abstract

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.

Keywords: graph homomorphisms, minimal reducible bounds, additive hereditary graph property.

1991 Mathematics Subject Classification: 05C15, 05C55, 06B05.

References

[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.
[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.
[3]	J. Kratochví l and P. Mihók, Hom properties are uniquely factorisable into irreducible factors, to appear in Discrete Math.
[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.
[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.
[6]	J. Nesetril, V. Rödl, Partitions of Vertices, Comment. Math. Univ. Carolin. 17 (1976) 675-681.

Received 19 January 1999
Revised 7 September 1999