Abstract:
Rado constructed a (simple) denumerable graph R with the positive integers
as vertex set with the following edges: for given m and n with m < n, m is
adjacent to n if n has a 1 in the mth position of its binary expansion. It is well known
that R is a universal graph in the set Ic of all countable graphs (since every graph in
Ic is isomorphic to an induced subgraph of R) and that it is a homogeneous graph
(since every isomorphism between two finite induced subgraphs of R extends to an
automorphism of R). In this paper we construct a graphU(H) which is H-universal in
→Hc, the induced-hereditary hom-property of H-colourable graphs consisting of all
(countable) graphs which have a homomorphism into a given (countable) graph H. If
H is the (finite) complete graph Kk , then→Hc is the property of k-colourable graphs.
The universal graph U(H) is characterised by showing that it is, up to isomorphism,
the unique denumerable, H-universal graph in →Hc which is H-homogeneous in
→Hc. The graphs H for which U(H)
∼=
R are also characterised.With small changes
to the definitions, our results translate effortlessly to hold for digraphs too. Another
slight adaptation of our work yields related results for (k, l)-split graphs.
