Looseness ranges of triangulations on closed surfaces. (English) Zbl 1084.05023

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.


05C10 Planar graphs; geometric and topological aspects of graph theory


Full Text: DOI


[1] Arocha, J.L.; Bracho, J.; Neumann-Lara, V., On the minimum size of tight hypergraphs, J. graph theory, 16, 319-326, (1992) · Zbl 0776.05079
[2] Arocha, J.L.; Bracho, J.; Neumann-Lara, V., Tight and untight triangulated surfaces, J. combin. theory, ser. B, 63, 185-199, (1995) · Zbl 0832.05035
[3] Nakamoto, A.; Negami, S.; Tanuma, T., Re-embedding structures of triangulations on closed surfaces, Sci. rep. Yokohama nat. univ., sect. I, math. phys. chem., 44, 41-55, (1997)
[4] S. Negami, Uniqueness and faithfulness of embedding of graphs into surfaces, Doctor Thesis, Tokyo Institute of Technology, 1985.
[5] Negami, S., Construction of graphs which are not uniquely and not faithfully embeddable in surfaces, Yokohama J. math., 33, 67-91, (1985) · Zbl 0593.05023
[6] Negami, S.; Midorikawa, T., Loosely-tightness of triangulations of closed surfaces, Sci. rep.Yokohama nat. univ., sect. I, math. phys. chem., 43, 25-41, (1996)
[7] Tanuma, T., One-loosely tight triangulations of closed surfaces, Yokohama math. J., 47, 203-211, (1999), (special issue) · Zbl 0947.05028
[8] Whitney, H., Congruent graphs and the connectivity of graphs, Amer. J. math., 54, 150-168, (1932) · JFM 58.0609.01
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.