The Planar Ramsey Numbers \(PR(K_4 – e, K_k – e)\)

Abstract

The planar Ramsey number \(PR(H_1, H_2)\) is the smallest integer \(n\) such that any planar graph on \(n\) vertices contains a copy of \(H_1\) or its complement contains a copy of \(H_2\). It is known that the Ramsey number \(R(K_4 – e, K_k – e)\) for \(k \leq 6\). In this paper, we prove that \(PR(K_4 – e, K_6 – e) = 16\) and show the lower bounds on \(PR(K_4 – e, K_k – e)\).