Planar Ramsey graphs (Q2327223): Difference between revisions

Summary: We say that a graph \(H\) is planar unavoidable if there is a planar graph \(G\) such that any red/blue coloring of the edges of \(G\) contains a monochromatic copy of \(H\), otherwise we say that \(H\) is planar avoidable. That is, \(H\) is planar unavoidable if there is a Ramsey graph for \(H\) that is planar. It follows from the four-color theorem and a result of \textit{D. Gonçalves} [in: Proceedings of the 37th annual ACM symposium on theory of computing, STOC'05. Baltimore, MD, USA, May 22--24, 2005. New York, NY: Association for Computing Machinery (ACM). 504--512 (2005; Zbl 1192.05113)] that if a graph is planar unavoidable then it is bipartite and outerplanar. We prove that the cycle on 4 vertices and any path are planar unavoidable. In addition, we prove that all trees of radius at most 2 are planar unavoidable and there are trees of radius 3 that are planar avoidable. We also address the planar unavoidable notion in more than two colors.