The looseness of a triangulation G on a closed surface F2, denoted by ξ (G), is defined as the minimum number k such that for any surjection c : V (G) → {1, 2, . . . , k + 3}, there is a face uvw of G with c(u), c(v) and c(w) all distinct. We shall bound ξ (G) for triangulations G on closed surfaces by the independence number of G denoted by α(G). In particular, for a triangulation G on the sphere, we have [...] and this bound is sharp. For a triangulation G on a non-spherical surface F2, we have ξ (G) ≤ 2α(G) + l(F2) − 2, where l(F2) = [(2 − χ(F2))/2] with Euler characteristic χ(F2).
@article{bwmeta1.element.doi-10_7151_dmgt_1870,
author = {Atsuhiro Nakamoto and Seiya Negami and Kyoji Ohba and Yusuke Suzuki},
title = {Looseness and Independence Number of Triangulations on Closed Surfaces},
journal = {Discussiones Mathematicae Graph Theory},
volume = {36},
year = {2016},
pages = {545-554},
zbl = {1339.05079},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1870}
}
Atsuhiro Nakamoto; Seiya Negami; Kyoji Ohba; Yusuke Suzuki. Looseness and Independence Number of Triangulations on Closed Surfaces. Discussiones Mathematicae Graph Theory, Tome 36 (2016) pp. 545-554. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1870/
[1] K. Appel, W. Haken and J. Koch, Every planar map is four colorable, Illinois J. Math. 21 (1977) 429-567. | Zbl 0387.05010
[2] J.L. Arocha, J. Bracho and V. Neumann-Lara, On the minimum size of tight hypergraphs, J. Graph Theory 16 (1992) 319-326. doi:10.1002/jgt.3190160405[Crossref] | Zbl 0776.05079
[3] J.L. Arocha, J. Bracho and V. Neumann-Lara, Tight and untight triangulations surfaces by complete graphs, J. Combin. Theory Ser. B 63 (1995) 185-199. doi:10.1006/jctb.1995.1015[Crossref] | Zbl 0832.05035
[4] J. Czap, S. Jendroľ, F. Kardoš and J. Miškuf, Looseness of plane graphs, Graphs Combin. 27 (2011) 73-85. doi:10.1007/s00373-010-0961-6[Crossref] | Zbl 1234.05064
[5] S. Negami and T. Midorikawa, Loosely-tightness of triangulations of closed surfaces, Sci. Rep. Yokohama Nat. Univ., Sec. I 43 (1996) 25-41.
[6] S. Negami, Looseness ranges of traingulations on closed surfaces, Discrete Math. 303 (2005) 167-174. doi:10.1016/j.disc.2005.01.010[Crossref] | Zbl 1084.05023
[7] G. Ringel, Map Color Theorem (Springer-Verlag, Berlin Heidelberg, 1974). doi:10.1007/978-3-642-65759-7[Crossref] | Zbl 0287.05102
[8] T. Tanuma, One-loosely tight triangulations on closed surfaces, Yokohama Math. J. 47 (1999) 203-211. | Zbl 0947.05028