New Bounds on Some Ramsey Numbers

Abstract

We derive a new upper bound of $26$ for the Ramsey number $R(K_5–P_3,K_5)$, lowering the previous upper bound of $28$. This leaves $25\le R(K_5–P_5,K_5)\le 26$, improving on one of the three remaining open cases in Hendry’s table, which listed Ramsey numbers for pairs of graphs $(G,H)$ with $G$ and $H$ having five vertices.

We also show, with the help of a computer, that $R(B_2,B_6)=17$ and $R(B_2,B_7)=18$ by full enumeration of $(B_2,B_6)$-$good$ graphs and $(B_2,B_7)$-$good$ graphs, where $B_n$ is the book graph with $n$ triangular pages.