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
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.
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 mth position of its binary expansion. ...
For several decades graphs act as a powerful and flexible representation formalism in pattern recognition and related fields. For instance, graphs have been employed for specific tasks in image and video analysis, ...