# DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

# IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

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

# Discussiones Mathematicae Graph Theory

## ON UNIVERSAL GRAPHS FOR HOM-PROPERTIES

 Peter Mihók Department of Applied Mathematics Faculty of Economics, Technical University B. Nemcovej, 040 01 Košice, Slovak Republic and Mathematical Institute, Slovak Academy of Science Gresákova 6, 040 01 Košice, Slovak Republic e-mail: peter.mihok@tuke.sk Jozef Miskuf Institute of Mathematics Faculty of Science, P.J. Safárik University Jesenná 5, 041 54 Košice, Slovak Republic e-mail: jozef.miskuf@upjs.sk Gabriel Semanišin Institute of Computer Science Faculty of Science, P.J. Safárik University Jesenná 5, 041 54 Košice, Slovak Republic e-mail: gabriel.semanisin@upjs.sk

## Abstract

A graph property is any isomorphism closed class of simple graphs. For a simple finite graph H, let → H denote the class of all simple countable graphs that admit homomorphisms to H, such classes of graphs are called hom-properties. Given a graph property P, a graph G ∈ P is universal in P if each member of P is isomorphic to an induced subgraph of G. In particular, we consider universal graphs in → H and we give a new proof of the existence of a universal graph in → H, for any finite graph H.

Keywords: universal graph, weakly universal graph, hom-property, core.

2000 Mathematics Subject Classification: 05C15, 05C75.

## References

 [1] A. Bonato, A family of universal pseudo-homogeneous G-colourable graphs, Discrete Math. 247 (2002) 13-23, doi: 10.1016/S0012-365X(01)00158-3. [2] A. Bonato, Homomorphisms and amalgamation, Discrete Math. 270 (2003) 33-42, doi: 10.1016/S0012-365X(02)00864-6. [3] A. Bonato, A Course on the Web Graph, Graduate Studies in Mathematics, Volume 89, AMS (2008) ISBN 978-0-8218-4467-0. [4] M. Borowiecki, I. Broere, M. Frick, P. Mihók and G. Semanišin, Survey of Hereditary Properties of Graphs, Discuss. Math. Graph Theory 17 (1997) 5-50, doi: 10.7151/dmgt.1037. [5] P.J. Cameron, The random graph, in: R.L. Graham, J. Nesetril (eds.), Algorithms and Combinatorics 14 (Springer, New York, 1997). [6] G. Cherlin, S. Shelah and N. Shi, Universal Graphs with Forbidden Subgraphs and Algebraic Closure, Advances in Applied Mathematics 22 (1999) 454-491, doi: 10.1006/aama.1998.0641. [7] R. Cowen, S.H. Hechler and P. Mihók, Graph coloring compactness theorems equivalent to BPI, Scientia Math. Japonicae 56 (2002) 171-180. [8] R.L. Graham, M. Grötschel and L. Lovász, Handbook of Combinatorics (Elsevier Science B.V. Amsterdam, 1995). [9] P. Hell and J. Nesetril, The core of a graph, Discrete Math. 109 (1992) 117-126, doi: 10.1016/0012-365X(92)90282-K. [10] P. Hell and J. Nesetril, Graphs and Homomorphisms, Oxford Lecture Series In Mathematics and its Applications 28 (Oxford University Press, 2004). [11] P. Komjáth, Some remarks on universal graphs, Discrete Math. 199 (1999) 259-265, doi: 10.1016/S0012-365X(98)00339-2. [12] J. Kratochví l and P. Mihók, Hom-properties are uniquely factorizable into irreducible factors, Discrete Math. 213 (2000) 189-194, doi: 10.1016/S0012-365X(99)00179-X. [13] J. Kratochví l, P. Mihók and G. Semanišin, Graphs maximal with respect to hom-properties, Discuss. Math. Graph Theory 18 (1997) 77-88, doi: 10.7151/dmgt.1040. [14] J. Nesetril, Graph homomorphisms and their structures, Proc. Seventh Quadrennial International Conference on the Theory and Applications of Graphs 2 (1995) 825-832. [15] R. Rado, Universal graphs and universal functions, Acta Arith. 9 (1964) 331-340. [16] E.R. Scheinerman, On the Structure of Hereditary Classes of Graphs, J. Graph Theory 10 (1986) 545-551, doi: 10.1002/jgt.3190100414. [17] X. Zhu, 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.