Planar Ramsey graphs

Maria Axenovich, Ursula Schade, Carsten Thomassen, Torsten Ueckerdt

Research output: Contribution to journalJournal articleResearchpeer-review

30 Downloads (Pure)

Abstract

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.

Original languageEnglish
Article numberP4.9
JournalElectronic Journal of Combinatorics
Volume26
Issue number4
ISSN1097-1440
Publication statusPublished - 1 Jan 2019

Fingerprint

Dive into the research topics of 'Planar Ramsey graphs'. Together they form a unique fingerprint.

Cite this