A Note on Ramsey Numbers Involving Large Books

  • Meng Liu
  • Yusheng Li


For graphs $G$ and $H$, the Ramsey number $R(G,H)$ is the minimum integer $N$ such that any red/blue edge coloring of $K_N$ contains either a red $G$ or a blue $H$. Let $\chi(G)$ be the chromatic number of $G$, and $s(G)$ the minimum size of a color class over all proper vertex colorings of $G$ with $\chi(G)$ colors. A connected graph $H$ is called $G$-{\em good} if $R(G,H)= (\chi(G)-1)(|H|-1)+s(G)$. For graphs $G$ and $H$, it is shown $K_p+nH$ is $(K_2+G)$-{\em good}, where $n$ is double-exponential in terms of $p,|G|,|H|$, and $K_p+nH$ is $C_{2m+1}$-{\em good} for $n\ge (100q)^{8q^3}$, where $q=\max\{m,p,|H|\}$. Both proofs are short that avoids using the regularity method.

Article Number