Cyclically Colored Triangulations: Enumeration and Connectedness of Reconfiguration Graphs

Abstract

We study the connectedness and enumeration of reconfiguration graphs of valid triangulations of convex polygons whose vertices are cyclically colored with $j\ge 3$ colors, where every triangle has vertices of three pairwise distinct colors. For $j=3$, we settle a conjectural expectation of Acharya, Mütze, and Verciani: we prove that the twist graph ${\mathcal{H}}_{3k+2}$ is connected for every $k\ge 4$, whereas ${\mathcal{H}}_8$ and ${\mathcal{H}}_{11}$ are disconnected. Using a colored root-edge decomposition that induces Cartesian products in the state space, we obtain coupled recurrences for $T(3k)$ and $T(3k+2)$. The corresponding generating functions reduce to the equation $U(x)=1+xU(x{)}^4$, and the difference between the two consecutive families is given by the Raney number $T(3k+3)-T(3k+2)=R_{4,5}(k-1)$. For $j\ge 4$, reconfiguration is performed by validity-preserving diagonal flips. We extend the root-edge decomposition to all admissible classes $N\not\equiv 1(\mathrm{mod}j)$, obtaining, for each fixed $j$, a finite algebraic system of functional equations. We further prove that the flip graph ${\mathcal{G}}_N^{(j)}$ is connected whenever valid triangulations exist. Thus, the root-edge decomposition provides a unified structural framework for the enumeration and reconfiguration of cyclically colored triangulations.

22 pages, 6 figures