Vol. 38, No. 1, 1971

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 294: 1
Vol. 293: 1  2
Vol. 292: 1  2
Vol. 291: 1  2
Vol. 290: 1  2
Vol. 289: 1  2
Vol. 288: 1  2
Vol. 287: 1  2
Online Archive
The Journal
Editorial Board
Special Issues
Submission Guidelines
Submission Form
Author Index
To Appear
ISSN: 0030-8730
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