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

• Autorzy: Oleg V. Borodin , Anna O. Ivanova , Tommy R. Jensen
• 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

EN

graph; plane map; vertex degree; weight; light subgraph

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2014
• Tom: 34
• Numer: 3
• Strony: 539-546

Daty

wydano

2014-08-01

otrzymano

2013-01-21

poprawiono

2013-06-10

zaakceptowano

2013-06-10

online

2014-07-16

Twórcy

autor

Oleg V. Borodin

• Institute of Mathematics Siberian Branch Russian Academy of Sciences and Novosibirsk State University Novosibirsk, 630090, Russia

autor

Anna O. Ivanova

• Institute of Mathematics of Ammosov North-Eastern Federal University Yakutsk, 677891, Russia

autor

Tommy R. Jensen

• Kyungpook National University Republic of Korea

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]

Identyfikatory

DOI

10.7151/dmgt.1748