The Ramsey Number for a Forest versus Disjoint Union of Complete Graphs

Abstract

Given two graphs $G$ and $H$, the Ramsey number $R(G,H)$ is the minimum integer $N$ such that any coloring of the edges of $K_N$ in red or blue yields a red $G$ or a blue $H$. Let $v(G)$ be the number of vertices of $G$ and $\chi (G)$ be the chromatic number of $G$. Let $s(G)$ denote the chromatic surplus of $G$, the cardinality of a minimum color class taken over all proper colorings of $G$ with $\chi (G)$ colors. Burr showed that for a connected graph $G$ and a graph $H$ with $v(G)\ge s(H)$, $R(G,H)\ge (v(G)-1)(\chi (H)-1)+s(H)$. A connected graph $G$ is called $H$-good if $R(G,H)=(v(G)-1)(\chi (H)-1)+s(H)$. In this paper, we mainly confirm the Ramsey number for any tree $T_n$ versus $K_m\cup K_l$. Our result yields that $T_n$ is $K_m\cup K_l$-good.