Let 𝒦 be the class of all
countable graphs and let 𝒦p be the class of all members of 𝒦 which have no complete
subgraphs of cardinality p. R. Rado has constructed a graph U which is universal for
𝒦. In this paper U is shown to be homogeneous, in the sense of Fraissé.
Also a simple construction is given of a graph Gp which is homogeneous
and universal for 𝒦p (for each p ≧ 3) and the structure of these graphs is
investigated.
It is shown that if H is an infinite member of 𝒦p then H can be embedded in
Gp in such a way that every automorphism of H extends uniquely to an
automorphism of Gp. A similar result holds for U. Also, U and G3 have single-orbit
automorphisms, while if p > 3, then Gp has no such automorphism. Finally,
a result concerning vertex colorings of the graphs Gp is proved and used
to give a new proof of a Theorem of Folkman on vertex colorings of finite
graphs.
