ВЫСОТА 5–ЗВЕЗДЫ В ПЛОСКИХ НОРМАЛЬНЫХ КАРТАХ С МИНИМАЛЬНОЙ СТЕПЕНЬЮ 5

Рассматриваются нормальные плоские карты M₅ с минимальной степенью 5. Высота 5-звезды есть максимальная степень ее вершин. Через h(S₅) обозначим минимальную высоту 5-звезд с центром в 5-вершине в данной карте M₅. Известно, что существуют нормальные плоские карты M₅ с минимальной степенью 5 такие, что h(S₅) неограниченно велика. В 1940 г. Лебег доказал, что если

−−−−→

M₅ не содержит 4-звезд циклического типа (5,6,6,5) с центром в 5-вершине, то h(S₅) ≤ 41. В 2013 г. О. В. Бородин, А. О. Иванова и Т. Р. Йенсен понизили эту

−−−−→ оценку до 28 и дали конструкцию M₅ без (5,6,6,5)-звезд с h(S₅) = 20.

−−−−→ Доказано, что если M₅ не содержит 4-звезд циклического типа (5,6,6,5) с центром в 5-вершине, то h(S₅) ≤ 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.