Легкие 3-цепи в 3-многогранниках без смежных 3-граней

Легкие 3-цепи в 3-многогранниках без смежных 3-граней

Бородин О. В., Иванова A. O.
Сибирский математический журнал, 65, 2, 249-257 (2024)
Скачать статью

УДК 519.17 
DOI: 10.33048/smzh.2024.65.202

Аннотация:

Пусть $\omega_k$ — максимум минимальной суммы степеней вершин (веса) в $k$-вершинных цепях ($k$-цепях) 3-многогранников. Очевидно, что каждый 3-многогранник содержит вершину степени не больше 5, так что $\omega_{1} \le 5$. Еще в 1955 г. Коциг доказал, что $\omega_{2} \le 13$ (т. е. найдется ребро веса не больше 13), причем оценка точна.

В 1993 г. Андо, Ивасаки и Канеко доказали, что $\omega_{3} \le 21$, и эта оценка также неулучшаема ввиду конструкции Йендроля, найденной в 1997 г. В 1997 г. О. В. Бородин уточнил этот результат, показав, что $\omega_{3} \le 18$ верно для всех 3-многогранников с $\omega_{2} \ge 7$, но для 3-многогранников с $\omega_{2} \ge 8$ имеет место более сильная оценка $\omega_{3} \le 17$, причем неулучшаемость 18 была подтверждена О. В. Бородиным и др. в 2013 г., а неулучшаемость 17 была известна давно.

За последние три десятилетия большое число работ было посвящено задачам раскраски и структурным задачам на плоских графах, разреженных в том или ином смысле.

В данной статье рассматриваются 3-многогранники без смежных 3-циклов, т. е. не имеющие хордальных 4-циклов (иначе говоря, без $K_4 − \epsilon)$. Известно, что для таких 3-многогранников $\omega_{1} \le 4$ и, более того, $\omega_{2} \le 9$, где обе оценки точны (Бородин, 1992).

Доказано, что всякий 3-многогранник без хордальных 4-циклов содержит 3-цепь веса не более 15, т. е. $\omega_{3} \le 15$, и эта оценка неулучшаема.

Литература:
  1. Wernicke P. Über den kartographischen Vierfarbensatz // Math. Ann. 1904. V. 58. P. 413–426.
     
  2. Franklin P. The four color problem // Amer. J. Math. 1922. V. 44. P. 225–236.
     
  3. Borodin O. V., Ivanova A. O. An analogue of Franklin’s theorem // Discrete Math. 2016. V. 339, N 10. P. 2553–2556.
     
  4. Borodin O.V., Ivanova A.O. An extension of Franklin’s theorem // Sib. Electron. Math. Rep. 2020. V. 17. P. 1516–1521.
     
  5. Ferencov´a B., Madaras T. Light graphs in families of polyhedral graphs with prescribed minimum degree, face size, edge and dual edge weight // Discrete Math. 2010. V. 310, N 12. P. 1661–1675.
     
  6. Fijavz G., Juvan M., Mohar B., Skrekovski R. Planar graphs without cycles of specific lengths // Europ. J. Combinatorics. 2002. V. 23, N 4. P. 377–388.
     
  7. Hudak P., Maceková M., Madaras T., Siroczki P. More on the structure of plane graphs with prescribed degrees of vertices, faces, edges and dual edges // Ars Math. Contemp. 2017. V. 13, N 2. P. 355–366.
     
  8. Jendrol’ S. Paths with restricted degrees of their vertices in planar graphs // Czechoslovak Math. J. 1999. V. 49, N 3. P. 481–490.
     
  9. Jendrol’ S. A structural property of convex 3-polytopes // Geom. Dedicata. 1997. V. 68. P. 91–99.
     
  10. Jendrol’ S., Madaras T., On light subgraphs in plane graphs with minimum degree five // Discuss. Math. Graph Theory. 1996. V. 16. P. 207–217.
     
  11. Madaras T. Note on the weight of paths in plane triangulations of minimum degree 4 and 5 // Discuss. Math. Graph Theory. 2000. V. 20, N 2. P. 173–180.
     
  12. Madaras T. Two variations of Franklin’s theorem // Tatra Mt. Math. Publ. 2007. V. 36. P. 61–70.
     
  13. Mohar B., Skrekovski R., Voss H.-J. Light subgraphs in planar graphs of minimum degree 4 and edge-degree 9 // J. Graph Theory. 2003. V. 44. P. 261–295.
     
  14. Jendrol’ S., Voss H.-J. Light subgraphs of graphs embedded in the plane — a survey // AIP Conf. Proc. 2013. V. 313, N 4. P. 406–421.
     
  15. Borodin O. V., Ivanova A. O. New results about the structure of plane graphs: a survey // AIP Conf. Proc. 2017. V. 1907, N 1. P. 030051.
     
  16. Cranston D. W., West D. B. An introduction to the discharging method via graph coloring // Discrete Math. 2017. V. 340, N 4. P. 766–793.
     
  17. Kotzig A., West D. B. Contribution to the theory of Eulerian polyhedra // Mat.-Fyz. Casopis. 1955. V. 5. P. 101–113.
     
  18. Ando K., Iwasaki S., Kaneko A. Every 3-connected planar graph has a connected subgraph with small degree sum (Japanese) // Ann. Meeting Math. Soc. Japan. 1993.
     
  19. Borodin O. V. Minimal vertex degree sum of a 3-path in plane maps // Discuss. Math. Graph Theory. 1997. V. 17, N 2. P. 279–284.
     
  20. Borodin O. V., Ivanova A. O., Jensen T. R., Kostochka A. V., Yancey M. P. Describing 3-paths in normal plane maps // Discrete Math. 2013. V. 313, N 23. P. 2702–2711.
     
  21. Dvorák Z., Postle L. Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8 // J. Combin. Theory Ser. B. 2018. V. 129. P. 38–54.
     
  22. Borodin O. V. An extension of Kotzig’s theorem on the minimum weight of edges in 3-polytopes // Mathematica Slovaca. 1992. V. 42, N 4. P. 385–389.

Работа О. В. Бородина (постановка задачи, доказательство) поддержана Министерством науки и высшего образования России (проект FWNF-2022-0017). Работа А. О. Ивановой (детали доказательства, конструкция) поддержана Министерством науки и высшего образования России, соглашение № 075-02-2023-947 от 16 февраля 2023 г.

Бородин Олег Вениаминович
  1. Институт математики им. С. Л. Соболева СО РАН,
    пр. Академика Коптюга, 4, Новосибирск 630090

E-mail: brdnoleg@math.nsc.ru

Иванова Анна Олеговна (ORCID 0000-0002-6179-3740)
  1. Северо-Восточный федеральный университет имени М.К. Аммосова,
    ул. Кулаковского, 48, Якутск 677000

E-mail: shmgnanna@mail.ru

Статья поступила 17 октября 2023 г.
После доработки — 2 ноября 2023 г.
Принята к публикации 28 ноября 2023 г.