HEIGHT OF 5–STARS IN NORMAL PLANE MAPS WITH MINIMUM DEGREE 5

We consider a normal plane map M5 with minimum degree 5. The height of a 5-star is the maximum degree of its vertices. Denote by h(S5) the minimum height of 5-stars centered at a 5-vertex in a given M5. It is known that there are normal plane maps M5 with minimum degree 5 such that h(S5) is arbitrarily large. In 1940, Lebesgue proved that if an M5 has no cyclic 4-stars of type (−−−−→ 5, 6, 6,5) centered at a 5-vertex, then h(S5) ≤ 41. In 2013, O. V. Borodin, A. O. Ivanova, and T. R. Jensen lowered this bound to 28 and constructed an M5 without (−−−−→ 5, 6, 6,5)-stars having h(S5) = 20. We prove that if an M5 has no cyclic 4-stars of type (−−−−→ 5, 6, 6,5) centered at a 5 vertex, then h(S5) ≤ 23.

1. Wernicke P. Uber den Kartographischen Vierfarbensatz // Math. Ann¨ 1904. V. 58. P. 413–426.

2. Franklin Ph. The four colour problem // Amer. J. Math 1922. V. 44. P. 225–236.

3. Lebesgue H. Quelques cons´equences simples de la formule d’Euler // J. Math. Pures Appl 1940. V. 19. P. 27–43.

4. Jendrol’ S., Madaras T. On light subgraphs in plane graphs of minimal degree five // Discuss. Math. Graph Theory. 1996. V. 16. P. 207–217.

5. Van den Heuvel J., McGuinness S. Coloring the square of a planar graph // J. Graph Theory. 2003. V. 42. P. 110–124.

6. Balogh J., Kochol M., Pluha´r A., Yu X. Covering planar graphs with forests // J. Comb. Theory, Ser. B. 2005. V. 94. P. 147–158.

7. Harant J., Jendrol’ S. On the existence of specific stars in planar graphs // Graphs Comb 2007. V. 23. P. 529–543.

8. Borodin O. V., Ivanova A. O. Describing (d − 2)-stars at d-vertices, d ≤ 5, in normal plane maps // Discrete Math 2013. V. 313, N 17. P. 1700–1709.

9. Borodin O. V., Ivanova A. O. Describing 4-stars at 5-vertices in normal plane maps with minimum degree 5 // Discrete Math 2013. V. 313, N 17. P. 1710–1714.

10. Borodin O. V., Ivanova A. O., Jensen T. R. 5-Stars of low weight in normal plane maps with minimum degree 5 // Discuss. Math. Graph Theory. 2014. V. 34, N 3. P. 539–546.