A family of universal pseudo-homogeneous \(G\)-colourable graphs (Q1598787)

The infinite random graph \(R\) is the unique countable graph such that, for all positive integers \(n\), for every \(n\)-subset \(S\) of \(V(R)\) and every partition of \(S\) into sets \(A\) and \(B\) (one of which might be empty) there is a vertex \(z\not\in S\) that is joined to each vertex in \(A\) and to no vertex in \(B\). Then, as shown by \textit{C. W. Henson} [Pac. J. Math. 38, 69-83 (1971; Zbl 0204.24103)], \(R\) is universal (it embeds all countable graphs as induced subgraphs) and homogeneous (each isomorphism between two finite induced subgraphs is induced by an automorphism). A graph \(G\) is \(G\)-colorable if it admits a homomorphism into \(G\). A finite graph is a core if every homomorphism of \(G\) to itself is an automorphism. For each finite core graph \(G\) there is a countable universal pseudo-homogeneous \(G\)-colorable graph \(M(G)\) that is unique up to isomorphism. The author investigates properties of \(M(G)\) similar to those of the infinite random graph, showing that \(M(G)\) has an independent dominating set and, for \(G\) connected, both one- and two-way Hamiltonian paths. He also answers a question of \textit{X. Caicedo} [Algebra Univers. 34, 314-321 (1995; Zbl 0837.08007)] concerning infinite antichains in the lattice of cores.