Monochromatic subgraphs in iterated triangulations

Abstract

For integers $n\ge 0$, an iterated triangulation $Tr(n)$ is defined recursively as follows: $Tr(0)$ is the plane triangulation on three vertices and, for $n\ge 1$, $Tr(n)$ is the plane triangulation obtained from the plane triangulation $Tr(n-1)$ by, for each inner face $F$ of $Tr(n-1)$, adding inside $F$ a new vertex and three edges joining this new vertex to the three vertices incident with $F$. In this paper, we show that there exists a 2-edge-coloring of $Tr(n)$ such that $Tr(n)$ contains no monochromatic copy of the cycle $C_k$ for any $k\ge 5$. As a consequence, the answer to one of two questions asked by Axenovich, Schade, Thomassen and Ueckerdt is negative. We also determine the radius two graphs $H$ for which there exists $n$ such that every 2-edge-coloring of $Tr(n)$ contains a monochromatic copy of $H$, extending a result of the above authors for radius two trees.