JavaScript is disabled for your browser. Some features of this site may not work without it.
Please note, we are experiencing high volume submissions; you will receive confirmations of submissions in due course. Data upload (DOI): https://researchdata.up.ac.za/ UPSpace: https://repository.up.ac.za/handle/2263/51914
Constructing universal graphs for induced-hereditary graph properties
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.
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. ...
We extend results about asymmetric colorings of finite Cartesian products of graphs to strong and direct products of graphs and digraphs. On the way we shorten proofs for the existence of prime factorizations of finite ...
We motivate, introduce, and study radicals on classes of graphs. This
concept, and the theory which is developed, imitates the original notion
of a Hoehnke radical in universal algebra using congruences. It is shown
how ...