On universal graphs for hom-properties

Peter Mihók; Jozef Miškuf; Gabriel Semanišin

Discussiones Mathematicae Graph Theory (2009)

  • Volume: 29, Issue: 2, page 401-409
  • ISSN: 2083-5892

Abstract

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

How to cite

top

Peter Mihók, Jozef Miškuf, and Gabriel Semanišin. "On universal graphs for hom-properties." Discussiones Mathematicae Graph Theory 29.2 (2009): 401-409. <http://eudml.org/doc/270831>.

@article{PeterMihók2009,
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.},
author = {Peter Mihók, Jozef Miškuf, Gabriel Semanišin},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {universal graph; weakly universal graph; hom-property; core; hom-property, core},
language = {eng},
number = {2},
pages = {401-409},
title = {On universal graphs for hom-properties},
url = {http://eudml.org/doc/270831},
volume = {29},
year = {2009},
}

TY - JOUR
AU - Peter Mihók
AU - Jozef Miškuf
AU - Gabriel Semanišin
TI - On universal graphs for hom-properties
JO - Discussiones Mathematicae Graph Theory
PY - 2009
VL - 29
IS - 2
SP - 401
EP - 409
AB - 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.
LA - eng
KW - universal graph; weakly universal graph; hom-property; core; hom-property, core
UR - http://eudml.org/doc/270831
ER -

References

top
  1. [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. Zbl0997.05032
  2. [2] A. Bonato, Homomorphisms and amalgamation, Discrete Math. 270 (2003) 33-42, doi: 10.1016/S0012-365X(02)00864-6. Zbl1024.03046
  3. [3] A. Bonato, A Course on the Web Graph, Graduate Studies in Mathematics, Volume 89, AMS (2008) ISBN 978-0-8218-4467-0. Zbl1142.05072
  4. [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. Zbl0902.05026
  5. [5] P.J. Cameron, The random graph, in: R.L. Graham, J. Nesetril (eds.), Algorithms and Combinatorics 14 (Springer, New York, 1997). Zbl0864.05076
  6. [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. Zbl0928.03049
  7. [7] R. Cowen, S.H. Hechler and P. Mihók, Graph coloring compactness theorems equivalent to BPI, Scientia Math. Japonicae 56 (2002) 171-180. Zbl1023.05048
  8. [8] R.L. Graham, M. Grötschel and L. Lovász, Handbook of Combinatorics (Elsevier Science B.V. Amsterdam, 1995). Zbl0833.05001
  9. [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. Zbl0803.68080
  10. [10] P. Hell and J. Nesetril, Graphs and Homomorphisms, Oxford Lecture Series In Mathematics and its Applications 28 (Oxford University Press, 2004). Zbl1062.05139
  11. [11] P. Komjáth, Some remarks on universal graphs, Discrete Math. 199 (1999) 259-265, doi: 10.1016/S0012-365X(98)00339-2. Zbl0930.05082
  12. [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. Zbl0949.05025
  13. [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. Zbl0905.05038
  14. [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. [15] R. Rado, Universal graphs and universal functions, Acta Arith. 9 (1964) 331-340. Zbl0139.17303
  16. [16] E.R. Scheinerman, On the Structure of Hereditary Classes of Graphs, J. Graph Theory 10 (1986) 545-551, doi: 10.1002/jgt.3190100414. Zbl0609.05057
  17. [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 Zbl0864.05037

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.