Planar Ramsey Numbers for Small Graphs

摘要

Given two graphs G_1 and G_2, the planar Ramsey number PR(G_1,G_2) is the smallest integer n such that every planar graph on n vertices either contains a copy of G_1 or its complement contains a copy of G_2. So far, the planar Ramsey numbers have been determined, when both, G_1 and G_2 are complete graphs or both are cycles. By combining computer search with some theoretical results, in this paper we compute most of the planar Ramsey numbers PR(G_1,G_2), where each of G_1 and G_2 is a complete graph, a cycle or a complete graph without one edge.