Planar Ramsey graphs

MaRDI QIDQ2327223zbMATH OpenFDO

Authors Ursula Schade, Carsten Thomassen, Torsten Ueckerdt, Maria Axenovich

Publication date 14 October 2019

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1812.00832

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

factorizationplanar unavoidable graphRamsey graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Generalized Ramsey theory (05C55) Ramsey theory (05D10)

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. I.e., $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 Gonc{c}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.

Review text

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.

Recommendations

• Planar Ramsey Numbers
• Complete graph-tree planar Ramsey numbers
• Planar Ramsey numbers for cycles
• Planar graph colorings without short monochromatic cycles
• Planar graph coloring avoiding monochromatic subgraphs: Trees and paths make it difficult

Cites work

• Bounded diameter arboricity
• Caterpillar arboricity of planar graphs
• Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
• Edge partition of planar sraphs into two outerplanar graphs
• Edge-Disjoint Spanning Trees of Finite Graphs
• Every planar map is four colorable. I: Discharging
• scientific article; zbMATH DE number 3661342 (Why is no real title available?)
• scientific article; zbMATH DE number 524135 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• On the degrees of the vertices of a directed graph
• On the linear vertex-arboricity of a planar graph
• Planar graph coloring avoiding monochromatic subgraphs: Trees and paths make it difficult
• Planar Ramsey numbers
• Planar Ramsey Numbers
• Star arboricity of graphs
• The Analogue of Ramsey Numbers for Planar Graphs
• The Game of Hex and the Brouwer Fixed-Point Theorem
• The Ramsey property for graphs with forbidden complete subgraphs
• The star arboricity of graphs

Cited in

(7)

• Monochromatic subgraphs in iterated triangulations
• Planar anti-Ramsey numbers of paths and cycles
• Note on (semi-)proper orientation of some triangulated planar graphs
• Minimal unavoidable sets of cycles in plane graphs
• QUADRILATERAL-TREE PLANAR RAMSEY NUMBERS
• Ramsey properties of products of chains
• Planar Ramsey numbers for cycles

This page was built for publication: Planar Ramsey graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2327223)