Vol. 38, No. 1, 1971

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 327: 1  2
Vol. 326: 1  2
Vol. 325: 1  2
Vol. 324: 1  2
Vol. 323: 1  2
Vol. 322: 1  2
Vol. 321: 1  2
Vol. 320: 1  2
Online Archive
The Journal
Editorial Board
Submission Guidelines
Submission Form
Policies for Authors
ISSN: 1945-5844 (e-only)
ISSN: 0030-8730 (print)
Special Issues
Author Index
To Appear
Other MSP Journals
A family of countable homogeneous graphs

C. Ward Henson

Vol. 38 (1971), No. 1, 69–83

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.

Mathematical Subject Classification 2000
Primary: 05C99
Received: 17 February 1971
Published: 1 July 1971
C. Ward Henson