Article ID Journal Published Year Pages File Type
4649449 Discrete Mathematics 2009 5 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,