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

Oleg V. Borodin; Anna O. Ivanova; Tommy R. Jensen

Discussiones Mathematicae Graph Theory (2014)

- Volume: 34, Issue: 3, page 539-546
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topOleg V. Borodin, Anna O. Ivanova, and Tommy R. Jensen. "5-Stars of Low Weight in Normal Plane Maps with Minimum Degree 5." Discussiones Mathematicae Graph Theory 34.3 (2014): 539-546. <http://eudml.org/doc/267939>.

@article{OlegV2014,

abstract = {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},

author = {Oleg V. Borodin, Anna O. Ivanova, Tommy R. Jensen},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {graph; plane map; vertex degree; weight; light subgraph},

language = {eng},

number = {3},

pages = {539-546},

title = {5-Stars of Low Weight in Normal Plane Maps with Minimum Degree 5},

url = {http://eudml.org/doc/267939},

volume = {34},

year = {2014},

}

TY - JOUR

AU - Oleg V. Borodin

AU - Anna O. Ivanova

AU - Tommy R. Jensen

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

JO - Discussiones Mathematicae Graph Theory

PY - 2014

VL - 34

IS - 3

SP - 539

EP - 546

AB - 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

LA - eng

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

UR - http://eudml.org/doc/267939

ER -

## References

top- [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] Zbl1059.05081
- [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] Zbl0927.05069
- [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). Zbl0977.05036
- [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). Zbl1012.05074
- [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] Zbl1277.05044
- [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] Zbl1277.05144
- [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] Zbl1140.05020
- [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] Zbl1008.05065
- [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] Zbl0877.05050
- [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. Zbl1150.05321
- [13] A. Kotzig, From the theory of eulerian polyhedra, Mat. Čas. 13 (1963) 20-34 (in Russian). Zbl0134.19601
- [14] H. Lebesgue, Quelques cons´equences simples de la formule d’Euler , J. Math. Pures Appl. 19 (1940) 27-43. Zbl0024.28701
- [15] P. Wernicke, Ü ber den kartographischen Vierfarbensatz , Math. Ann. 58 (1904) 413-426. doi:10.1007/BF01444968 [Crossref]

## NotesEmbed ?

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