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

Abstract

top
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

How to cite

top

Oleg 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. [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. [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. [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. [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. [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. [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. [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. [8] P. Franklin, The four colour problem, Amer. J. Math. 44 (1922) 225-236. doi:10.2307/2370527[Crossref] 
  9. [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. [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. [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. [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. [13] A. Kotzig, From the theory of eulerian polyhedra, Mat. Čas. 13 (1963) 20-34 (in Russian). Zbl0134.19601
  14. [14] H. Lebesgue, Quelques cons´equences simples de la formule d’Euler , J. Math. Pures Appl. 19 (1940) 27-43. Zbl0024.28701
  15. [15] P. Wernicke, Ü ber den kartographischen Vierfarbensatz , Math. Ann. 58 (1904) 413-426. doi:10.1007/BF01444968 [Crossref] 

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.