Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649449 | Discrete Mathematics | 2009 | 5 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Anthony Bonato, Paweł Prałat,