Homomorphisms and amalgamation Original Research Article

We prove that for each finite core graph G, the class of all graphs admitting a homomorphism into G is a pseudo-amalgamation class, in the sense of Fraı̈ssé. This fact gives rise to a countably infinite universal pseudo-homogeneous graph which shares some of the properties of the infinite random graph. Our methods apply simultaneously to G-colourings in several classes of relational structures, such as the classes of directed graphs or hypergraphs.