Constructing universal graphs for induced-hereditary graph properties

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 m'th 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). In this paper we construct graphs which are universal in or for P for di erent inducedhereditary properties P of countable graphs. Constructions of universal graphs for the graph properties containing all graphs with colouring-number at most k+1 and k-degenerate graphs are obtained by restricting the edges of R. Results on the properties of these graphs are given and relationships between them are explored. This is followed by a general recursive construction which proves the existence of a countable universal graph for any induced-hereditary property of countable general graphs. A general construction of universal graphs for products of properties of graphs is also presented. The paper is concluded by a comparison between the two types of constructions of universal graphs.