
arXiv: 1812.00832
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.
ddc:004, FOS: Computer and information sciences, Discrete Mathematics (cs.DM), DATA processing & computer science, Ramsey theory, Generalized Ramsey theory, Ramsey graph, 004, Planar graphs; geometric and topological aspects of graph theory, factorization, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), 05D10, 05C55, 05C10, info:eu-repo/classification/ddc/004, planar unavoidable graph, Computer Science - Discrete Mathematics
ddc:004, FOS: Computer and information sciences, Discrete Mathematics (cs.DM), DATA processing & computer science, Ramsey theory, Generalized Ramsey theory, Ramsey graph, 004, Planar graphs; geometric and topological aspects of graph theory, factorization, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), 05D10, 05C55, 05C10, info:eu-repo/classification/ddc/004, planar unavoidable graph, Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 1 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
