Minimal reducible bounds for hom-properties of graphs

• Autorzy: Amelie Berger , Izak Broere
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

graph homomorphisms; minimal reducible bounds; additive hereditary graph property

Kategorie tematyczne

• 06B05: Structure theory
• 05C15: Coloring of graphs and hypergraphs
• 05C55: Generalized Ramsey theory

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 1999
• Tom: 19
• Numer: 2
• Strony: 143-158

Daty

wydano

1999

otrzymano

1999-01-19

poprawiono

1999-09-07

Twórcy

autor

Amelie Berger

• Department of Mathematics, Rand Afrikaans University, P.O. Box 524, Auckland Park, 2006 South Africa

autor

Izak Broere

• Department of Mathematics, Rand Afrikaans University, P.O. Box 524, Auckland Park, 2006 South Africa

Bibliografia

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

Identyfikatory

DOI

10.7151/dmgt.1091