Looseness and Independence Number of Triangulations on Closed Surfaces

• Autorzy: Atsuhiro Nakamoto , Seiya Negami , Kyoji Ohba , Yusuke Suzuki
• Języki publikacji: EN

Abstrakty

EN

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).

Słowa kluczowe

EN

triangulations; closed surfaces; looseness; k-loosely tight; independence number

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2016
• Tom: 36
• Numer: 3
• Strony: 545-554

Daty

wydano

2016-08-01

otrzymano

2015-04-13

poprawiono

2015-09-08

zaakceptowano

2015-09-08

online

2016-07-06

Twórcy

autor

Atsuhiro Nakamoto

• Graduate School of Environment and Information Science Yokohama National University 79-7 Tokiwadai, Hodogaya-Ku, Yokohama 240-8501, Japan

autor

Seiya Negami

• Graduate School of Environment and Information Science Yokohama National University 79-7 Tokiwadai, Hodogaya-Ku, Yokohama 240-8501, Japan

autor

Kyoji Ohba

• Yonago National College of Technology Yonago, Tottori 683-8502, Japan

autor

Yusuke Suzuki

• Department of Mathematics Niigata University 8050 Ikarashi 2-no-cho, Nishi-ku, Niigata, 950-2181, Japan

Bibliografia

• [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[Crossref]
• [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]
• [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]
• [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]
• [7] G. Ringel, Map Color Theorem (Springer-Verlag, Berlin Heidelberg, 1974). doi:10.1007/978-3-642-65759-7[Crossref]
• [8] T. Tanuma, One-loosely tight triangulations on closed surfaces, Yokohama Math. J. 47 (1999) 203-211.

Identyfikatory

DOI

10.7151/dmgt.1870