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, Tome 34 (2014), p. 539-546 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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

Publié le : 2014-01-01
EUDML-ID : urn:eudml:doc:267939 
@article{bwmeta1.element.doi-10_7151_dmgt_1748,
     author = {Oleg V. Borodin and Anna O. Ivanova and Tommy R. Jensen},
     title = {5-Stars of Low Weight in Normal Plane Maps with Minimum Degree 5},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {34},
     year = {2014},
     pages = {539-546},
     zbl = {1310.05063},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1748}
}

Oleg V. Borodin; Anna O. Ivanova; Tommy R. Jensen. 5-Stars of Low Weight in Normal Plane Maps with Minimum Degree 5. Discussiones Mathematicae Graph Theory, Tome 34 (2014) pp. 539-546. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1748/

[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] | Zbl 1059.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] | Zbl 0927.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). | Zbl 0977.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). | Zbl 1012.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] | Zbl 1277.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] | Zbl 1277.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] | Zbl 1140.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] | Zbl 1008.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] | Zbl 0877.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. | Zbl 1150.05321

[13] A. Kotzig, From the theory of eulerian polyhedra, Mat. Čas. 13 (1963) 20-34 (in Russian). | Zbl 0134.19601

[14] H. Lebesgue, Quelques cons´equences simples de la formule d’Euler , J. Math. Pures Appl. 19 (1940) 27-43. | Zbl 0024.28701

[15] P. Wernicke, Ü ber den kartographischen Vierfarbensatz , Math. Ann. 58 (1904) 413-426. doi:10.1007/BF01444968 [Crossref]