The good, the bad, and the great: Homomorphisms and cores of random graphs |
| |
Authors: | Anthony Bonato Pawe? Pra?at |
| |
Institution: | a Department of Mathematics, Wilfrid Laurier University, Waterloo, ON, Canada b Department of Mathematics and Statistics, Dalhousie University, Halifax, NS, Canada |
| |
Abstract: | We consider homomorphism properties of a random graph G(n,p), where p is a function of n. A core H is great if for all e∈E(H), there is some homomorphism from H−e to H that is not onto. Great cores arise in the study of uniquely H-colourable graphs, where two inequivalent definitions arise for general cores H. For a large range of p, we prove that with probability tending to 1 as n→∞, 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 H-colourable coincide. |
| |
Keywords: | Graph homomorphism Core Great core Random graph |
本文献已被 ScienceDirect 等数据库收录! |
|