A family of universal pseudo-homogeneous G-colourable graphs
A family of universal pseudo-homogeneous \(G\)-colourable graphs
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.
- The good, the bad, and the great: homomorphisms and cores of random graphs
- Homomorphisms and amalgamation
- Universal Horn classes and color families of graphs
- On a problem of Cameron's on inexhaustible graphs
- On representing words in the automorphism group of the random graph
- Universal \(H\)-colourable graphs
- scientific article; zbMATH DE number 3954977 (Why is no real title available?)
This page was built for publication: A family of universal pseudo-homogeneous \(G\)-colourable graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1598787)
