PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2014 | 34 | 3 | 539-546
Tytuł artykułu

5-Stars of Low Weight in Normal Plane Maps with Minimum Degree 5

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
It is known that there are normal plane maps M5 with minimum degree 5 such that the minimum degree-sum w(S5) of 5-stars at 5-vertices is arbitrarily large. In 1940, Lebesgue showed that if an M5 has no 4-stars of cyclic type (5, 6, 6, 5) centered at 5-vertices, then w(S5) ≤ 68. We improve this bound of 68 to 55 and give a construction of a (5, 6, 6, 5)-free M5 with w(S5) = 48
Słowa kluczowe
Wydawca
Rocznik
Tom
34
Numer
3
Strony
539-546
Opis fizyczny
Daty
wydano
2014-08-01
otrzymano
2013-01-21
poprawiono
2013-06-10
zaakceptowano
2013-06-10
online
2014-07-16
Twórcy
  • Institute of Mathematics Siberian Branch Russian Academy of Sciences and Novosibirsk State University Novosibirsk, 630090, Russia, brdnoleg@math.nsc.ru
  • Institute of Mathematics of Ammosov North-Eastern Federal University Yakutsk, 677891, Russia, shmgnanna@mail.ru
Bibliografia
  • [1] J. Balogh, M. Kochol, A. Pluh´ar and X. Yu, Covering planar graphs with forests, J. Combin. Theory (B) 94 (2005) 147-158. doi:10.1016/j.jctb.2004.12.002[Crossref]
  • [2] O.V. Borodin, Solution of Kotzig’s and Gr¨unbaum’s problems on the separability of a cycle in a planar graph, Mat. Zametki 46(5) (1989) 9-12 (in Russian).
  • [3] O.V. Borodin and D.R. Woodall, Short cycles of low weight in normal plane maps with minimum degree 5, Discuss. Math. Graph Theory 18 (1998) 159-164. doi:10.7151/dmgt.1071 [Crossref]
  • [4] O.V. Borodin, H.J. Broersma, A.N. Glebov and J. Van den Heuvel, The structure of plane triangulations in terms of clusters and stars, Diskretn. Anal. Issled. Oper. Ser. 1 8(2) (2001) 15-39 (in Russian).
  • [5] O.V. Borodin, H.J. Broersma, A.N. Glebov and J. Van den Heuvel, Minimal degrees and chromatic numbers of squares of planar graphs, Diskretn. Anal. Issled. Oper. Ser. 1 8(4) (2001) 9-33 (in Russian).
  • [6] O.V. Borodin and A.O. Ivanova, Describing (d − 2)-stars at d-vertices, d≤ 5, in normal plane maps, Discrete Math. 313 (2013) 1700-1709. doi:10.1016/j.disc.2013.04.026[WoS][Crossref]
  • [7] O.V. Borodin and A.O. Ivanova, Describing 4-stars at 5-vertices in normal plane maps with minimum degree 5, Discrete Math. 313 (2013) 1710-1714. doi:10.1016/j.disc.2013.04.025[WoS][Crossref]
  • [8] P. Franklin, The four colour problem, Amer. J. Math. 44 (1922) 225-236. doi:10.2307/2370527[Crossref]
  • [9] J. Harant and S. Jendrol’, On the existence of specific stars in planar graphs, Graphs Combin. 23 (2007) 529-543. doi:10.1007/s00373-007-0747-7[Crossref]
  • [10] J. Van den Heuvel and S. McGuinness, Coloring the square of a planar graph, J. Graph Theory 42 (2003) 110-124. doi:10.1002/jgt.10077[Crossref]
  • [11] S. Jendrol’ and T. Madaras, On light subgraphs in plane graphs of minimal degree five, Discuss. Math. Graph Theory 16 (1996) 207-217. doi:10.7151/dmgt.1035[Crossref]
  • [12] S. Jendrol’ and T. Madaras, Note on an existence of small degree vertices with at most one big degree neighbour in planar graphs, Tatra Mt. Math. Publ. 30 (2005) 149-153.
  • [13] A. Kotzig, From the theory of eulerian polyhedra, Mat. Čas. 13 (1963) 20-34 (in Russian).
  • [14] H. Lebesgue, Quelques cons´equences simples de la formule d’Euler , J. Math. Pures Appl. 19 (1940) 27-43.
  • [15] P. Wernicke, Ü ber den kartographischen Vierfarbensatz , Math. Ann. 58 (1904) 413-426. doi:10.1007/BF01444968 [Crossref]
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1748
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.