Geodesic
Looseness and Independence Number of Triangulations on Closed Surfaces
Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 3, pp. 545-554.

Voir la notice de l'article provenant de la source Library of Science

The looseness of a triangulation G on a closed surface F^2, 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 ξ (G) ≤11 α (G) - 10/6and this bound is sharp. For a triangulation G on a non-spherical surface F^2, we have ξ (G) ≤ 2 α (G) + 𝓁(F^2) − 2, where 𝓁(F^2) = (2 − χ (F^2))//2 with Euler characteristic χ (F^2).
Keywords: triangulations, closed surfaces, looseness, k-loosely tight, independence number 
@article{DMGT_2016_36_3_a2,
     author = {Nakamoto, Atsuhiro and Negami, Seiya and Ohba, Kyoji and Suzuki, Yusuke},
     title = {Looseness and {Independence} {Number} of {Triangulations} on {Closed} {Surfaces}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {545--554},
     publisher = {mathdoc},
     volume = {36},
     number = {3},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a2/}
}
TY  - JOUR
AU  - Nakamoto, Atsuhiro
AU  - Negami, Seiya
AU  - Ohba, Kyoji
AU  - Suzuki, Yusuke
TI  - Looseness and Independence Number of Triangulations on Closed Surfaces
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2016
SP  - 545
EP  - 554
VL  - 36
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a2/
LA  - en
ID  - DMGT_2016_36_3_a2
ER  - 
%0 Journal Article
%A Nakamoto, Atsuhiro
%A Negami, Seiya
%A Ohba, Kyoji
%A Suzuki, Yusuke
%T Looseness and Independence Number of Triangulations on Closed Surfaces
%J Discussiones Mathematicae. Graph Theory
%D 2016
%P 545-554
%V 36
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a2/
%G en
%F DMGT_2016_36_3_a2
Nakamoto, Atsuhiro; Negami, Seiya; Ohba, Kyoji; Suzuki, Yusuke. Looseness and Independence Number of Triangulations on Closed Surfaces. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 3, pp. 545-554. http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a2/

[1] K. Appel, W. Haken and J. Koch, Every planar map is four colorable, Illinois J. Math. 21 (1977) 429-567.

[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

[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

[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

[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

[7] G. Ringel, Map Color Theorem (Springer-Verlag, Berlin Heidelberg, 1974). doi:10.1007/978-3-642-65759-7

[8] T. Tanuma, One-loosely tight triangulations on closed surfaces, Yokohama Math. J. 47 (1999) 203-211.