Ramsey numbers of trees versus fans

Yanbo Zhang, Haitze J. Broersma, Yaojun Chen

    Research output: Contribution to journalArticleAcademicpeer-review

    5 Citations (Scopus)
    70 Downloads (Pure)


    For two given graphs G1 and G2, the Ramsey number R(G1, G2) is the smallest integerN such that, for any graph G of order N, either G contains G1 as a subgraph or the complement of G contains G2 as a subgraph. Let Tn be a tree of order n, Sn a star of order n, and Fm a fan of order 2m + 1, i.e., m triangles sharing exactly one vertex. In this paper, we prove that R(Tn, Fm) = 2n − 1 for n ≥ 3m^2 − 2m − 1, and if Tn = Sn, then the range can be replaced by n ≥ max{m(m − 1) + 1, 6(m − 1)}, which is tight in some sense.
    Original languageEnglish
    Pages (from-to)994-999
    Number of pages6
    JournalDiscrete mathematics
    Issue number6
    Publication statusPublished - Jun 2015


    • Tree
    • Star
    • Fan
    • Ramsey number
    • 22/4 OA procedure


    Dive into the research topics of 'Ramsey numbers of trees versus fans'. Together they form a unique fingerprint.

    Cite this