ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory


Discussiones Mathematicae Graph Theory  17(1) (1997)   77-88
DOI: 10.7151/dmgt.1040


Jan Kratochvíl

Department of Applied Mathematics
Charles University
Malostranské nám. 25, 118 00 Praha 1, Czech Republic


Peter Mihók

Mathematical Institute
Slovak Academy of Sciences
Grešákova 6, 040 01 Košice, Slovak Republic

e-mail: mihok@Koš

Gabriel Semanišin

Department of Geometry and Algebra
Faculty of Science, P. J. Šafárik University
Jesenná 5, 041 54 Košice, Slovak Republic



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.

Keywords: hom-property of graphs, hereditary property of graphs, maximal graphs.

1991 Mathematics Subject Classification: 05C15, 05C35, 05C75.


[1] M. Borowiecki and P. Mihók, Hereditary Properties of Graphs, in: Advances in Graph Theory (Vishwa International Publications, 1991) 41-68.
[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.
[3] R.L. Graham, M. Grötschel and L. Lovász, Handbook of Combinatorics (Elsevier Science B.V. Amsterdam, 1995).
[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.
[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.
[6] T.R. Jensen and B. Toft, Graph Colouring Problems (Wiley-Interscience Publications New York, 1995).
[7] J. Kratochví l and P. Mihók, Hom-properties are uniquely factorizable into irreducible factors (submitted).
[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.
[9] P. Mihók and G. Semanišin, On the chromatic number of reducible hereditary properties (submitted).
[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.
[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] 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.