The Ramsey Number $r(K_5-P_3,K_5)$

Luis Boza


For two given graphs $G_1$ and $G_2$, the Ramsey number $r(G_1,G_2)$ is the smallest integer $n$ such that for any graph $G$ of order $n$, either $G$ contains $G_1$ or the complement of $G$ contains $G_2$. Let $K_m$ denote a complete graph of order $m$ and $K_n-P_3$ a complete graph of order $n$ without two incident edges. In this paper, we prove that $r(K_5-P_3,K_5)=25$ without help of computer algorithms.

Full Text: