Graphs maximal with respect to hom-properties

Jan Kratochvíl; Peter Mihók; Gabriel Semanišin

Discussiones Mathematicae Graph Theory (1997)

  • Volume: 17, Issue: 1, page 77-88
  • ISSN: 2083-5892

Abstract

top
For a simple graph H, →H denotes the class of all graphs that admit homomorphisms to H (such classes of graphs are called hom-properties). We investigate hom-properties from the point of view of the lattice of hereditary properties. In particular, we are interested in characterization of maximal graphs belonging to →H. We also provide a description of graphs maximal with respect to reducible hom-properties and determine the maximum number of edges of graphs belonging to →H.

How to cite

top

Jan Kratochvíl, Peter Mihók, and Gabriel Semanišin. "Graphs maximal with respect to hom-properties." Discussiones Mathematicae Graph Theory 17.1 (1997): 77-88. <http://eudml.org/doc/270745>.

@article{JanKratochvíl1997,
abstract = {For a simple graph H, →H denotes the class of all graphs that admit homomorphisms to H (such classes of graphs are called hom-properties). We investigate hom-properties from the point of view of the lattice of hereditary properties. In particular, we are interested in characterization of maximal graphs belonging to →H. We also provide a description of graphs maximal with respect to reducible hom-properties and determine the maximum number of edges of graphs belonging to →H.},
author = {Jan Kratochvíl, Peter Mihók, Gabriel Semanišin},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {hom-property of graphs; hereditary property of graphs; maximal graphs; homomorphisms; hom-properties; characterization},
language = {eng},
number = {1},
pages = {77-88},
title = {Graphs maximal with respect to hom-properties},
url = {http://eudml.org/doc/270745},
volume = {17},
year = {1997},
}

TY - JOUR
AU - Jan Kratochvíl
AU - Peter Mihók
AU - Gabriel Semanišin
TI - Graphs maximal with respect to hom-properties
JO - Discussiones Mathematicae Graph Theory
PY - 1997
VL - 17
IS - 1
SP - 77
EP - 88
AB - For a simple graph H, →H denotes the class of all graphs that admit homomorphisms to H (such classes of graphs are called hom-properties). We investigate hom-properties from the point of view of the lattice of hereditary properties. In particular, we are interested in characterization of maximal graphs belonging to →H. We also provide a description of graphs maximal with respect to reducible hom-properties and determine the maximum number of edges of graphs belonging to →H.
LA - eng
KW - hom-property of graphs; hereditary property of graphs; maximal graphs; homomorphisms; hom-properties; characterization
UR - http://eudml.org/doc/270745
ER -

References

top
  1. [1] M. Borowiecki and P. Mihók, Hereditary Properties of Graphs, in: Advances in Graph Theory (Vishwa International Publications, 1991) 41-68. 
  2. [2] I. Broere, M. Frick and G. Semanišin, Maximal graphs with respect to hereditary properties, Discussiones Mathematicae Graph Theory 17 (1997) 51-66, doi: 10.7151/dmgt.1038. Zbl0902.05027
  3. [3] R.L. Graham, M. Grötschel and L. Lovász, Handbook of Combinatorics (Elsevier Science B.V. Amsterdam, 1995). Zbl0833.05001
  4. [4] P. Hell and J. Nešetril, The core of a graph, Discrete Math. 109 (1992) 117-126, doi: 10.1016/0012-365X(92)90282-K. Zbl0803.68080
  5. [5] P. Hell and J. Nešetril, Complexity of H-coloring, J. Combin. Theory (B) 48 (1990) 92-110, doi: 10.1016/0095-8956(90)90132-J. Zbl0639.05023
  6. [6] T.R. Jensen and B. Toft, Graph Colouring Problems (Wiley-Interscience Publications New York, 1995). 
  7. [7] J. Kratochví l and P. Mihók, Hom-properties are uniquely factorizable into irreducible factors (submitted). 
  8. [8] P. Mihók and G. Semanišin, Reducible properties of graphs, Discussiones Math. Graph Theory 15 (1995) 11-18, doi: 10.7151/dmgt.1002. Zbl0829.05057
  9. [9] P. Mihók and G. Semanišin, On the chromatic number of reducible hereditary properties (submitted). Zbl1055.05061
  10. [10] J. Nešetril, Graph homomorphisms and their structures, in: Proc. Seventh Quadrennial International Conference on the Theory and Applications of Graphs 2 (1995) 825-832. Zbl0858.05049
  11. [11] M. Simonovits, Extremal graph theory, in: L.W. Beineke and R.J. Wilson, eds., Selected Topics in Graph Theory vol. 2, (Academic Press, London, 1983) 161-200. 
  12. [12] X. Zhou, Uniquely H-colourable graphs with large girth, J. Graph Theory 23 (1996) 33-41, doi: 10.1002/(SICI)1097-0118(199609)23:1<33::AID-JGT3>3.0.CO;2-L 

Citations in EuDML Documents

top
  1. Anthony Bonato, A note on uniquely H-colourable graphs
  2. Izak Broere, Marietjie Frick, Gabriel Semanišin, Maximal graphs with respect to hereditary properties
  3. Gabriel Semanišin, On some variations of extremal graph problems
  4. Amelie Berger, Izak Broere, Minimal reducible bounds for hom-properties of graphs
  5. Stefan A. Burr, Michael S. Jacobson, Peter Mihók, Gabriel Semanišin, Generalized ramsey theory and decomposable properties of graphs
  6. Peter Mihók, Jozef Miškuf, Gabriel Semanišin, On universal graphs for hom-properties

NotesEmbed ?

top

You must be logged in to post comments.