Abstract | ||
---|---|---|
We determine the structure of {C3,C5}-free 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(mod5), for some k. This answers a question of Messuti and Schacht. We deduce that the homomorphism threshold of {C3,C5}-free graphs is 1/5, thus answering a question of Oberkampf and Schacht. |
Year | DOI | Venue |
---|---|---|
2019 | 10.1002/jgt.22369 | JOURNAL OF GRAPH THEORY |
Keywords | Field | DocType |
homomorphic threshold,large minimum degree,odd girth | Graph,Combinatorics,Homomorphism,Mathematics | Journal |
Volume | Issue | ISSN |
90 | 1 | 0364-9024 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Shoham Letzter | 1 | 5 | 7.28 |
Richard Snyder | 2 | 1 | 1.04 |