Planar Ramsey numbers for cycles (Q941377)

The planar Ramsey number \(\text{PR}(G,H)\) is the least \(n\) such that every \(n\)-vertex planar graph \(F\) contains either \(G\) or its complement contains \(H\). The paper determines all planar Ramsey numbers when \(G\) and \(H\) are cycles. The key idea is that the complement of a planar graph is very dense, and therefore is almost Hamiltonian. For example, Theorem 4 asserts that the complement of every planar graph on \(n\geq 9\) vertices contains \(C_{n-2}\), which implies that \(\text{PR}(C_m,C_n)\leq n+2\) whenever \(n\geq 7\). The matching bound \(\text{PR}(C_m,C_n)\geq n+2\) for \(m\geq 5\) is due the graph \(K_{2,n-1}\).