ArticleOriginal scientific text
Title
Minimal reducible bounds for hom-properties of graphs
Authors 1, 1
Affiliations
- Department of Mathematics, Rand Afrikaans University, P.O. Box 524, Auckland Park, 2006 South Africa
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
Bibliography
- 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.
- P. Hell and J. Nesetril, The core of a graph, Discrete Math. 109 (1992) 117-126, doi: 10.1016/0012-365X(92)90282-K.
- J. Kratochví l and P. Mihók, Hom properties are uniquely factorisable into irreducible factors, to appear in Discrete Math.
- 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.
- 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.
- J. Nesetril, V. Rödl, Partitions of Vertices, Comment. Math. Univ. Carolin. 17 (1976) 675-681.
Pages:
143-158
Main language of publication
English
Received
1999-01-19
Accepted
1999-09-07
Published
1999
DOI: 10.7151/dmgt.1091
Exact and natural sciences