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 \leq R(K_5 – P_5, K_5) \leq 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.