Computing the Ramsey Number \(R(K_{5}-P_{3}, K_{5})\)

Jesse A.Calvert1, Michael J.Schuster2, Stanislaw P.Radziszowski3
1Department of Mathema, North Washington University St. Louis, MO 63105
2 Department of Mathematics, Carolina State University Raleigh, NC 27695
3Department of Computer Science, Rochester Institute of Technology Rochester, NY

Abstract

We give a computer-assisted proof of the fact that \( R(K_5 – P_3, K_5) = 25 \). This solves one of the three remaining open cases in Hendry’s table, which listed the Ramsey numbers for pairs of graphs on 5 vertices. We find that there exist no \( (K_5 – P_3, K_5) \)-good graphs containing a \( K_4 \) on 23 or 24 vertices, where a graph \( F \) is \( (G, H) \)-good if \( F \) does not contain \( G \) and the complement of \( F \) does not contain \( H \). The unique \( (K_5 – P_3, K_5) \)-good graph containing a \( K_4 \) on 22 vertices is presented.