PL EN

Preferencje
Język
Widoczny [Schowaj] Abstrakt
Liczba wyników
Czasopismo

Discussiones Mathematicae Graph Theory

2016 | 36 | 3 | 545-554
Tytuł artykułu

Looseness and Independence Number of Triangulations on Closed Surfaces

Autorzy
Treść / Zawartość
Warianty tytułu
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
Wydawca
Czasopismo
Rocznik
Tom
Numer
Strony
545-554
Opis fizyczny
Daty
wydano
2016-08-01
otrzymano
2015-04-13
poprawiono
2015-09-08
zaakceptowano
2015-09-08
online
2016-07-06
Twórcy
autor
• Graduate School of Environment and Information Science Yokohama National University 79-7 Tokiwadai, Hodogaya-Ku, Yokohama 240-8501, Japan, nakamoto@ynu.ac.jp
autor
• Graduate School of Environment and Information Science Yokohama National University 79-7 Tokiwadai, Hodogaya-Ku, Yokohama 240-8501, Japan, negami@ynu.ac.jp
autor
autor
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.
Typ dokumentu
Bibliografia
Identyfikatory