Looseness ranges of triangulations on closed surfaces (Q2576861)

A triangulation of a closed surface is tight if every 3-coloring of its vertices that uses all three colors has a face that is incident with vertices of all three colors. A tight triangulation has its underlying graph complete, but the converse is not true. The looseness of a triangulation is the minimum \(k\) such that every \((k+3)\)--coloring of its vertices using all colors has a face incident with vertices of all three colors. Given a graph \(G\) and a closed surface \(F^2\), define \(\zeta_{\min}\) (\(\zeta_{\max}\)) as the minimum (respectively maximum) looseness over all triangulations \(G\) of \(F^2\). The authors show that \(\zeta_{\max} - \zeta_{\min} \leq 2 \lfloor (2 - \chi(F^2))/2 \rfloor\), where \(\chi(F^2)\) is the Euler characteristic of \(F^2\). As a corollary, any two triangulations of the projective plane with the same graph have the same looseness.