Discussiones Mathematicae Graph Theory 29(2) (2009) 401-409
doi: 10.7151/dmgt.1455

[BIBTex] [PDF] [PS]

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.

Received 20 January 2008
Revised 8 July 2009
Accepted 8 July 2009