Download PDF - On universal graphs for hom-propertiesAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

On universal graphs for hom-properties

Authors 1, 2, 3, 4

Affiliations

  1. Department of Applied Mathematics, Faculty of Economics, Technical University, B. Nĕmcovej, 040 01 Košice, Slovak Republic
  2. Mathematical Institute, Slovak Academy of Science, Gresákova 6, 040 01 Košice, Slovak Republic
  3. Institute of Mathematics, Faculty of Science, P.J. Šafárik University, Jesenná 5, 041 54 Košice, Slovak Republic
  4. Institute of Computer Science, Faculty of Science, P.J. Šafárik University, Jesenná 5, 041 54 Košice, Slovak Republic

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 , 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.

Keywords

ENG
universal graph, weakly universal graph, hom-property, core

Bibliography

  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
Discussiones Mathematicae Graph Theory
2009/29/2
Export to PBN, Opens in new tab
Pages:
401-409
Main language of publication
English
Received
2008-01-20
Accepted
2009-07-08
Published
2009

DOI: 10.7151/dmgt.1455

Exact and natural sciences