On universal graphs for hom-properties
Author(s) -
Peter Mihók,
J. Miškuf,
Gabriel Semanišin
Publication year - 2009
Publication title -
discussiones mathematicae graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.476
H-Index - 19
eISSN - 2083-5892
pISSN - 1234-3099
DOI - 10.7151/dmgt.1455
Subject(s) - mathematics , combinatorics , discrete mathematics
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 This research was supported in part by Slovak VEGA grant 2/7141/27. The research of the author was supported in part by VEGA Grant 1/0035/09, Slovak APVV grant 0007-07. 402 P. Mihok, J. Miskuf and G. Semanisin 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 .
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom