Looseness and Independence Number of Triangulations on Closed Surfaces

Atsuhiro Nakamoto; Seiya Negami; Kyoji Ohba; Yusuke Suzuki

Discussiones Mathematicae Graph Theory (2016)

  • Volume: 36, Issue: 3, page 545-554
  • ISSN: 2083-5892

Abstract

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

How to cite

top

Atsuhiro Nakamoto, et al. "Looseness and Independence Number of Triangulations on Closed Surfaces." Discussiones Mathematicae Graph Theory 36.3 (2016): 545-554. <http://eudml.org/doc/285660>.

@article{AtsuhiroNakamoto2016,
abstract = {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).},
author = {Atsuhiro Nakamoto, Seiya Negami, Kyoji Ohba, Yusuke Suzuki},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {triangulations; closed surfaces; looseness; k-loosely tight; independence number; -loosely tight},
language = {eng},
number = {3},
pages = {545-554},
title = {Looseness and Independence Number of Triangulations on Closed Surfaces},
url = {http://eudml.org/doc/285660},
volume = {36},
year = {2016},
}

TY - JOUR
AU - Atsuhiro Nakamoto
AU - Seiya Negami
AU - Kyoji Ohba
AU - Yusuke Suzuki
TI - Looseness and Independence Number of Triangulations on Closed Surfaces
JO - Discussiones Mathematicae Graph Theory
PY - 2016
VL - 36
IS - 3
SP - 545
EP - 554
AB - 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).
LA - eng
KW - triangulations; closed surfaces; looseness; k-loosely tight; independence number; -loosely tight
UR - http://eudml.org/doc/285660
ER -

References

top
  1. [1] K. Appel, W. Haken and J. Koch, Every planar map is four colorable, Illinois J. Math. 21 (1977) 429-567. Zbl0387.05010
  2. [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] Zbl0776.05079
  3. [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] Zbl0832.05035
  4. [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] Zbl1234.05064
  5. [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. [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] Zbl1084.05023
  7. [7] G. Ringel, Map Color Theorem (Springer-Verlag, Berlin Heidelberg, 1974). doi:10.1007/978-3-642-65759-7[Crossref] Zbl0287.05102
  8. [8] T. Tanuma, One-loosely tight triangulations on closed surfaces, Yokohama Math. J. 47 (1999) 203-211. Zbl0947.05028

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.