Geodesic
5-stars of low weight in normal plane maps with minimum degree 5
Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 3, pp. 539-546.

Voir la notice de l'article provenant de la source Library of Science

It is known that there are normal plane maps M_5 with minimum degree 5 such that the minimum degree-sum w(S_5) of 5-stars at 5-vertices is arbitrarily large. In 1940, Lebesgue showed that if an M_5 has no 4-stars of cyclic type (5, 6, 6, 5) centered at 5-vertices, then w(S_5) ≤ 68. We improve this bound of 68 to 55 and give a construction of a (5, 6, 6, 5)-free M_5 with w(S_5) = 48.
Keywords: graph, plane map, vertex degree, weight, light subgraph 
@article{DMGT_2014_34_3_a5,
     author = {Borodin, Oleg V. and Ivanova, Anna O. and Jensen, Tommy R.},
     title = {5-stars of low weight in normal plane maps with minimum degree 5},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {539--546},
     publisher = {mathdoc},
     volume = {34},
     number = {3},
     year = {2014},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2014_34_3_a5/}
}
TY  - JOUR
AU  - Borodin, Oleg V.
AU  - Ivanova, Anna O.
AU  - Jensen, Tommy R.
TI  - 5-stars of low weight in normal plane maps with minimum degree 5
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2014
SP  - 539
EP  - 546
VL  - 34
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2014_34_3_a5/
LA  - en
ID  - DMGT_2014_34_3_a5
ER  - 
%0 Journal Article
%A Borodin, Oleg V.
%A Ivanova, Anna O.
%A Jensen, Tommy R.
%T 5-stars of low weight in normal plane maps with minimum degree 5
%J Discussiones Mathematicae. Graph Theory
%D 2014
%P 539-546
%V 34
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2014_34_3_a5/
%G en
%F DMGT_2014_34_3_a5
Borodin, Oleg V.; Ivanova, Anna O.; Jensen, Tommy R. 5-stars of low weight in normal plane maps with minimum degree 5. Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 3, pp. 539-546. http://geodesic.mathdoc.fr/item/DMGT_2014_34_3_a5/

[1] J. Balogh, M. Kochol, A. Pluhár and X. Yu, Covering planar graphs with forests, J. Combin. Theory (B) 94 (2005) 147-158. doi:10.1016/j.jctb.2004.12.002

[2] O.V. Borodin, Solution of Kotzig’s and Grünbaum’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

[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

[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

[8] P. Franklin, The four colour problem, Amer. J. Math. 44 (1922) 225-236. doi:10.2307/2370527

[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

[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

[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

[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équences 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