On signed diagonal flip sequences (Q627936): Difference between revisions

A ``diagonal flip'' is performed on a triangulation of a polygon by locating two triangles whose intersection consists of a single edge, removing that edge to obtain a quadrilateral, and then inserting the other diagonal of that quadrilateral. \textit{S. Eliahou} [Eur. J. Comb. 20, No. 7, 641--646 (1999; Zbl 0938.05030)] and \textit{Si.I. Kryuchkov} [``Four Color Theorem and Trees,'' I.V. Kurchatov Institute of Atomic Energy IAE-5537/1, Moscow (1992)] introduced a signed version of the diagonal flip operation, and conjectured that signed diagonal flips suffice to connect any two triangulations of the same polygon. They also observed that if true, the conjecture would imply the four-color theorem. \textit{S. Gravier} and \textit{C. Payan} [Eur. J. Comb. 23, No. 7, 817--821 (2002; Zbl 1012.05069)] proved the conjecture by verifying the converse of this observation: the four-color theorem implies the conjecture. In the paper under review, the author characterizes the sequences of diagonal flips that can be transformed into sequences of signed diagonal flips. Given a sequence \(\varphi=(\varphi(1),\dots,\varphi(k))\) of diagonal flips, construct a \(k\)-vertex graph \(\tilde{G}(\varphi)\) whose \(i\)th and \(j\)th vertices (\(i<j\)) are adjacent if and only if one of the triangles created by \(\varphi(i)\) is later removed by \(\varphi(j)\). Then there is a signed version of \(\varphi\) if and only if \(G(\varphi)\) is bipartite.