The homomorphism threshold of    {   C  3   ,   C  5   }   ‐free graphs | Zendy

Letzter Shoham | Zendy; Snyder Richard | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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) - mathematics , homomorphism , combinatorics , graph homomorphism , discrete mathematics , pancyclic graph , graph , symmetric graph , 1 planar graph , chordal graph , line graph , graph power , voltage graph

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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research