On the Ramsey Number for Cycle with Respect to Identical Copies of Complete Graphs

Abstract

For graphs $G$ and $H$, Ramsey number $R(G,H)$ is the smallest natural number $n$ such that no $(G,H)$-free graph on $n$ vertices exists. In 1981, Burr [5] proved the general lower bound $R(G,H)\ge (n–1)(\chi (H)–1)+\sigma (H)$, where $G$ is a connected graph of order $n$, $\chi (H)$ denotes the chromatic number of $H$ and $\sigma (H)$ is its chromatic surplus, namely, the minimum cardinality of a color class taken over all proper colorings of $H$ with $\chi (H)$ colors. A connected graph $G$ of order $n$ is called good with respect to $H$, $H$-good, if $R(G,H)=(n–1)(\chi (H)–1)+\sigma (H)$. The notation $t{K}_m$ represents a graph with $t$ identical copies of complete graph $K_m$. In this note, we discuss the goodness of cycle $C_n$ with respect to $t{K}_m$ for $m,t\ge 2$ and sufficiently large $n$. Furthermore, it is also provided the Ramsey number $R(G,t{K}_m)$, where $G$ is a disjoint union of cycles.