Abstract

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 G_p 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 G_p in such a way that every automorphism of H extends uniquely to an automorphism of G_p. A similar result holds for U. Also, U and G₃ have single-orbit automorphisms, while if p > 3, then G_p has no such automorphism. Finally, a result concerning vertex colorings of the graphs G_p is proved and used to give a new proof of a Theorem of Folkman on vertex colorings of finite graphs.

Mathematical Subject Classification 2000

Milestones

Authors