About

Log in?

DTU users get better search results including licensed content and discounts on order fees.

Anyone can log in and get personalized features such as favorites, tags and feeds.

Log in as DTU user Log in as non-DTU user No thanks

DTU Findit

Journal article

Planar Ramsey graphs

From

Karlsruhe Institute of Technology1

Algorithms and Logic, Department of Applied Mathematics and Computer Science, Technical University of Denmark2

Department of Applied Mathematics and Computer Science, Technical University of Denmark3

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

DTU users get better search results including licensed content and discounts on order fees.

Log in as DTU user

Access

Analysis