Premium
The homomorphism threshold of { C 3 , C 5 } ‐free graphs
Author(s) -
Letzter Shoham,
Snyder Richard
Publication year - 2019
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22369
Subject(s) - homomorphism , mathematics , combinatorics , graph homomorphism , graph , discrete mathematics , pancyclic graph , degree (music) , 1 planar graph , chordal graph , line graph , graph power , physics , acoustics
We determine the structure of { C 3 , C 5 } ‐free graphs with n vertices and minimum degree larger than n / 5 : such graphs are homomorphic to the graph obtained from a ( 5 k − 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 3 , C 5 } ‐free graphs is 1/5, thus answering a question of Oberkampf and Schacht.