Journal article
Planar Ramsey graphs
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 Goncalves 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.
Language: | English |
---|---|
Publisher: | The Electronic Journal of Combinatorics |
Year: | 2019 |
ISSN: | 10778926 and 10971440 |
Types: | Journal article |
DOI: | 10.37236/8366 |
ORCIDs: | Thomassen, Carsten |