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 Gonçalves 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.
@article{10_37236_8366,
author = {Maria Axenovich and Ursula Schade and Carsten Thomassen and Torsten Ueckerdt},
title = {Planar {Ramsey} graphs},
journal = {The electronic journal of combinatorics},
year = {2019},
volume = {26},
number = {4},
doi = {10.37236/8366},
zbl = {1422.05066},
url = {http://geodesic.mathdoc.fr/articles/10.37236/8366/}
}
TY - JOUR
AU - Maria Axenovich
AU - Ursula Schade
AU - Carsten Thomassen
AU - Torsten Ueckerdt
TI - Planar Ramsey graphs
JO - The electronic journal of combinatorics
PY - 2019
VL - 26
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/8366/
DO - 10.37236/8366
ID - 10_37236_8366
ER -
