The homomorphism threshold of -free graphs |
| |
| Authors: | Shoham Letzter Richard Snyder |
| |
| Institution: | 1. Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, CB3 0WB Cambridge, United Kingdom;2. Department of Mathematical Sciences, University of Memphis, Memphis, Tennessee |
| |
| Abstract: | We determine the structure of  -free graphs with n vertices and minimum degree larger than  : such graphs are homomorphic to the graph obtained from a  -cycle by adding all chords of length  , for some k. This answers a question of Messuti and Schacht. We deduce that the homomorphism threshold of  -free graphs is 1/5, thus answering a question of Oberkampf and Schacht. |
| |
| Keywords: | homomorphic threshold large minimum degree odd girth |
|
|
