Narrowing down the gap on cycle-star Ramsey numbers

Yanbo Zhang, Haitze J. Broersma, Yaojun Chen

    Research output: Contribution to journalArticleAcademicpeer-review

    Abstract

    Given two graphs G1 and G2, the Ramsey number R(G1,G2) is the smallest integer N such that, for any graph G of order N, either G1 is a subgraph of G, or G2 is a subgraph of the complement of G. Let Cm denote a cycle of order m, K1,n a star of order n + 1 and Wn a wheel of order n + 1. Already back in the 1970s, exact values of the Ramsey numbers R(Cm,K1,n) have been determined for all m ≥ 2n and for all odd m ≤ 2n − 1, but for even m < 2n not many exact values are known. In this paper, we use a result of Bondy on pancyclicity to fill a considerable part of this gap. We show that R(Cm,K1,n) = 2n for even m with n < m < 2n, and that R(Cm,K1,n) = 2m−1 for even m with 3n/4+1 ≤ m ≤ n. In addition, we determine another six formerly unknown exact values of Ramsey numbers, namely R(C6,K1,n) for 7 ≤ n ≤ 11, and R(C6,W9).
    Original languageUndefined
    Pages (from-to)481-493
    Number of pages13
    JournalJournal of combinatorics (Somerville)
    Volume7
    Issue number2-3
    DOIs
    Publication statusPublished - Feb 2016

    Keywords

    • EWI-26877
    • MSC-05C
    • Cycle
    • IR-100080
    • Star
    • METIS-316849
    • Ramsey number

    Cite this