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\le 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)$.