The good, the bad, and the great: Homomorphisms and cores of random graphs

We consider homomorphism properties of a random graph G(n,p)G(n,p), where pp is a function of nn. A core HH is great if for all e∈E(H)e∈E(H), there is some homomorphism from H−eH−e to HH that is not onto. Great cores arise in the study of uniquely HH-colourable graphs, where two inequivalent definitions arise for general cores HH. For a large range of pp, we prove that with probability tending to 1 as n→∞n→∞, G∈G(n,p)G∈G(n,p) is a core that is not great. Further, we give a construction of infinitely many non-great cores where the two definitions of uniquely HH-colourable coincide.