Letzter, S;
Snyder, R;
(2019)
The homomorphism threshold of {C₃,C₅}-free graphs.
Journal of Graph Theory
, 90
(1)
pp. 83-106.
10.1002/jgt.22369.
Preview |
Text
hom_revision.pdf - Accepted Version Download (372kB) | Preview |
Abstract
We determine the structure of {C₃,C₅}-free graphs graphs with n vertices and minimum degree larger than n/5: such graphs are homomorphic to the graph obtained from a (5k - 3)-cycle by adding all chords of length 1(mod 5), for some k . This answers a question of Messuti and Schacht. We deduce that the homomorphism threshold of {C₃,C₅}-free graphs is 1/5, thus answering a question of Oberkampf and Schacht.
| Type: | Article |
|---|---|
| Title: | The homomorphism threshold of {C₃,C₅}-free graphs |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1002/jgt.22369 |
| Publisher version: | https://doi.org/10.1002/jgt.22369 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher's terms and conditions. |
| Keywords: | homomorphic threshold, large minimum degree, odd girth |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics |
| URI: | https://discovery-pp.ucl.ac.uk/id/eprint/10107273 |
Archive Staff Only
 |
View Item |
