The Ramsey Numbers \(R(C_{\leq n}, K_m)\)

Abstract

Let\(ex(m, C_{\leq n})\) denote the maximum size of a graph of order \(m\) and girth at least \(n+1\), and \(EX(m, C_{\leq n})\) be the set of all graphs of girth at least \(n+1\) and size \(ex(m, C_{\leq n})\). The Ramsey number \(R(C_{\leq n}, K_m)\) is the smallest \(k\) such that every graph of order \(k\) contains either a cycle of order \(n\) for some \(3 \leq l \leq n\) or a set of \(m\) independent vertices. It is known that \(ex(2n, C_{\leq n}) = 2n + 2\) for \(n \geq 4\), and the exact values of \(R(C_{\leq n}, K_m)\) for \(n \geq m\) are known. In this paper, we characterize all graphs in \(EX(2n, C_{\leq n})\) for \(n \geq 5\), and then obtain the exact values of \(R(C_{\leq n}, K_m)\) for \(m \in \{n, n+1\}\).