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. 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) and that it is a homogeneous graph
(since every isomorphism between two finite induced subgraphs of R extends to an
automorphism of R). In this paper we construct a graphU(H) which is H-universal in
→Hc, the induced-hereditary hom-property of H-colourable graphs consisting of all
(countable) graphs which have a homomorphism into a given (countable) graph H. If
H is the (finite) complete graph Kk , then→Hc is the property of k-colourable graphs.
The universal graph U(H) is characterised by showing that it is, up to isomorphism,
the unique denumerable, H-universal graph in →Hc which is H-homogeneous in
→Hc. The graphs H for which U(H)
R are also characterised.With small changes
to the definitions, our results translate effortlessly to hold for digraphs too. Another
slight adaptation of our work yields related results for (k, l)-split 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 m'th 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, ...
The accessibility to handwritten historical documents is often constrained by the limited feasibility of automatic full transcriptions. Keyword Spotting (KWS), that allows to retrieve arbitrary query words from documents, ...