Monochromatic subgraphs in iterated triangulations

Jie Ma¹ ; Tianyun Tang¹ ; Xingxing Yu²

¹University of Science and Technology of China
²Georgia Institute of Technology

The electronic journal of combinatorics, Tome 27 (2020) no. 4

Résumé

For integers $n\ge 0$, an iterated triangulation $\mathrm{Tr}(n)$ is defined recursively as follows: $\mathrm{Tr}(0)$ is the plane triangulation on three vertices and, for $n\ge 1$, $\mathrm{Tr}(n)$ is the plane triangulation obtained from the plane triangulation $\mathrm{Tr}(n-1)$ by, for each inner face $F$ of $\mathrm{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 $\mathrm{Tr}(n)$ such that $\mathrm{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 et al. is negative. We also determine the radius 2 graphs $H$ for which there exists $n$ such that every 2-edge-coloring of $\mathrm{Tr}(n)$ contains a monochromatic copy of $H$, extending a result of Axenovich et al. for radius 2 trees.

Détail

DOI : 10.37236/9292

Classification : 05C55, 05C10, 05D10
Mots-clés : 2-edge-coloring of \(\text{Tr}(n)\)