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 𝓟, a graph G ∈ 𝓟 is universal in 𝓟 if each member of 𝓟 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.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1455,
author = {Peter Mih\'ok and Jozef Mi\v skuf and Gabriel Semani\v sin},
title = {On universal graphs for hom-properties},
journal = {Discussiones Mathematicae Graph Theory},
volume = {29},
year = {2009},
pages = {401-409},
zbl = {1194.05041},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1455}
}
Peter Mihók; Jozef Miškuf; Gabriel Semanišin. On universal graphs for hom-properties. Discussiones Mathematicae Graph Theory, Tome 29 (2009) pp. 401-409. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1455/
[000] [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. | Zbl 0997.05032
[001] [2] A. Bonato, Homomorphisms and amalgamation, Discrete Math. 270 (2003) 33-42, doi: 10.1016/S0012-365X(02)00864-6. | Zbl 1024.03046
[002] [3] A. Bonato, A Course on the Web Graph, Graduate Studies in Mathematics, Volume 89, AMS (2008) ISBN 978-0-8218-4467-0. | Zbl 1142.05072
[003] [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. | Zbl 0902.05026
[004] [5] P.J. Cameron, The random graph, in: R.L. Graham, J. Nesetril (eds.), Algorithms and Combinatorics 14 (Springer, New York, 1997). | Zbl 0864.05076
[005] [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. | Zbl 0928.03049
[006] [7] R. Cowen, S.H. Hechler and P. Mihók, Graph coloring compactness theorems equivalent to BPI, Scientia Math. Japonicae 56 (2002) 171-180. | Zbl 1023.05048
[007] [8] R.L. Graham, M. Grötschel and L. Lovász, Handbook of Combinatorics (Elsevier Science B.V. Amsterdam, 1995). | Zbl 0833.05001
[008] [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. | Zbl 0803.68080
[009] [10] P. Hell and J. Nesetril, Graphs and Homomorphisms, Oxford Lecture Series In Mathematics and its Applications 28 (Oxford University Press, 2004). | Zbl 1062.05139
[010] [11] P. Komjáth, Some remarks on universal graphs, Discrete Math. 199 (1999) 259-265, doi: 10.1016/S0012-365X(98)00339-2. | Zbl 0930.05082
[011] [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. | Zbl 0949.05025
[012] [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. | Zbl 0905.05038
[013] [14] J. Nesetril, Graph homomorphisms and their structures, Proc. Seventh Quadrennial International Conference on the Theory and Applications of Graphs 2 (1995) 825-832.
[014] [15] R. Rado, Universal graphs and universal functions, Acta Arith. 9 (1964) 331-340. | Zbl 0139.17303
[015] [16] E.R. Scheinerman, On the Structure of Hereditary Classes of Graphs, J. Graph Theory 10 (1986) 545-551, doi: 10.1002/jgt.3190100414. | Zbl 0609.05057
[016] [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 | Zbl 0864.05037