Minimal reducible bounds for hom-properties of graphs

Amelie Berger; Izak Broere

Discussiones Mathematicae Graph Theory (1999)

  • Volume: 19, Issue: 2, page 143-158
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Amelie Berger, and Izak Broere. "Minimal reducible bounds for hom-properties of graphs." Discussiones Mathematicae Graph Theory 19.2 (1999): 143-158. <http://eudml.org/doc/270586>.

@article{AmelieBerger1999,
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.},
author = {Amelie Berger, Izak Broere},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {graph homomorphisms; minimal reducible bounds; additive hereditary graph property; hom-property; homomorphism; additive hereditary properties},
language = {eng},
number = {2},
pages = {143-158},
title = {Minimal reducible bounds for hom-properties of graphs},
url = {http://eudml.org/doc/270586},
volume = {19},
year = {1999},
}

TY - JOUR
AU - Amelie Berger
AU - Izak Broere
TI - Minimal reducible bounds for hom-properties of graphs
JO - Discussiones Mathematicae Graph Theory
PY - 1999
VL - 19
IS - 2
SP - 143
EP - 158
AB - 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.
LA - eng
KW - graph homomorphisms; minimal reducible bounds; additive hereditary graph property; hom-property; homomorphism; additive hereditary properties
UR - http://eudml.org/doc/270586
ER -

References

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

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.