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

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

Бородин О. В., Иванова A. O.
Сибирский математический журнал, 66, 6, 1030-1036 (2025)
Скачать статью

УДК 519.17 
DOI: 10.33048/smzh.2025.66.603

Аннотация:

Вес $w (e)$ ребра $e$ в 3-многограннике это сумма степеней его концевых вершин. Ребро $e = uv$ есть ($i, j$)-ребро, если $d(u) \le i$ и $d(v) \le j$. В 1940 г. Лебег доказал, что каждый 3-многогранник содержит (3, 11)-ребро, или (4, 7)-ребро, или (5, 6)-ребро, где 7 и 6 неулучшаемы. В 1955 г. Коциг доказал, что каждый 3- многогранник содержит ребро с суммой степеней концевых вершин не более 13, причем граница точна. О. В. Бородин (1987), отвечая на вопрос Эрдеша, доказал, что каждый плоский граф без вершин степени меньше 3 содержит такое ребро. Более того, О. В. Бородин (1991) усилил этот результат, доказав, что найдется либо (3, 10)-ребро, или (4, 7)-ребро, или (5, 6)-ребро. Для 3-многогранников получены верхние оценки минимального веса (суммы степеней концевых вершин) всех его ребер, обозначаемого $w$; инцидентных 3-грани, $w^∗$ ; и инцидентных двум 3- граням, $w^{∗∗}$. В частности, О. В. Бородин (1996) доказал, что если $w^{∗∗} = \infty$, т. е. не существует ребер, инцидентных двум 3-граням, то либо $w^∗ \le 9$ либо $w \le 8$, где обе оценки неулучшаемы. Недавно мы усилили этот факт, доказав, что  $w^{∗∗} = \infty$ влечет наличие либо (3, 6)-ребра, либо (4, 4)-ребра, инцидентных с 3-гранью, либо иначе (3, 5)-ребра, причем описание точно. (Хорошо известно, что если (3, 5)-ребра присутствуют, то может вообще не быть 3-граней.) Цель нашей статьи — усилить вышеуказанный результат, доказав, что $w^{∗∗} = \infty$ влечет либо (3, 6)-ребро, окруженное 3-гранью и 4-гранью, либо (4, 4)-ребро, окруженное 3-гранью и $7^-$-гранью, либо (3, 5)-ребро, где ни один из параметров не может быть улучшен. Главной трудностью было построение 3-многогранника, подтверждающего точность 7 в данном описании.

Литература:
  1. Wernicke P. Über den Kartographischen Vierfarbensatz // Math. Ann. 19 04. V. 58, N 3. P. 413–426.
     
  2. Lebesgue H. Quelques conséquences simples de la formule d’Euler // J. Math. Pures Appl. 1940. V. 19. P. 27–43.
     
  3. Kotzig A. Contribution to the theory of Eulerian polyhedra (Slovak) // Mat. Čas. 1955. V. 5.  P. 101–103.
     
  4. Grünbaum B. New views on some old questions of combinatorial geometry // Int. Teorie Combinatorie, Rome (1973). 1976. V. 1. P. 451–468.
     
  5. Бородин О. В. Совместные раскраски графов на плоскости // Дискрет. анализ. 1987. Т. 45. С. 21–27.
     
  6. Borodin O. V. Joint extension of two Kotzig’s theorems on 3-polytopes // Combinatorica. 1992. V. 13, N 1. P. 121–125.
     
  7. Бородин О. В. Строение окрестностей ребра в плоском графе и совместная раскраска вершин, ребер и граней // Мат. заметки. 1993. Т. 53, № 5. С. 35–47.
     
  8. Бородин О. В. Совместное обобщение теорем Лебега и Коцига о комбинаторике плоских графов // Дискрет. математика. 1991. Т. 3, № 4. С. 24–27.
     
  9. Borodin O. V. Colorings of plane graphs: a survey // Discrete Math. 2013. V. 313, N 4. P. 517–539.
     
  10. Borodin O. V., Ivanova A. O. New results about the structure of plane graphs: a survey // AIP Conference Proceedings. 2017. N 1907. 030051.
     
  11. 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.
     
  12. Jendrol’ S., Voss H.-J. Light subgraphs of graphs embedded in the plane – a survey // Discrete Math. 2013. V. 313, N 4. P. 406–421.
     
  13. Aksenov V. A., Borodin O. V., Ivanova A. O. An extension of Kotzig’s theorem // Discussiones Math. Graph Theory. 2016. V. 36, N 4. P. 889–897.
     
  14. Batueva Ts. Ch-D., Borodin O. V., Bykov M. A., Ivanova A. O., Kazak O. N., Nikiforov D. V. Refined weight of edges in normal plane maps // Discrete Math. 2017. V. 340, N 11. P. 2659–2664.
     
  15. Borodin O. V. On the total coloring of planar graphs // J. Reine Angew. Math. 1989. V. 394. P. 180–185.
     
  16. Borodin O. V. Structural theorem on plane graphs with application to the entire coloring // J. Graph Theory. 1996. V. 23, N 3. P. 233–239.
     
  17. Borodin O. V. More about the weight of edges in planar graphs // Tatra Mountains Math. Publ. 1996. V. 9. P. 11–14.
     
  18. Borodin O. V., Hartke S. G., Ivanova A. O., Kostochka A. V., West D. B. (5, 2)-Coloring of sparse graphs // Sib. Electron. Mat. Izv. 2008. V. 5. P. 417–426.
     
  19. Borodin O. V., Glebov A. N., Raspaud A. Planar graphs without triangles adjacent to cycles of length from 4 to 7 are 3-colorable // Thomassen’s special issue of Discrete Math. 2010. V. 310, N 20. P. 2584–2594.
     
  20. Borodin O. V., Ivanova A. O. Weight of edges in normal plane maps // Discrete Math. 2016. V. 339, N 5. P. 1507–1511.
     
  21. Borodin O. V., Ivanova A. O. An improvement of Lebesgue’s description of edges in 3-polytopes and faces in plane quadrangulations // Discrete Math. 2019. V. 342, N 6. P. 1820–1827.
     
  22. Borodin O. V., Ivanova A. O., Kostochka A. V., Sheikh N. N. Minimax degrees of quasiplane graphs without 4-faces // Sib. Electron. Mat. Izv. 2007. V. 4. P. 435–439.
     
  23. Borodin O. V., Kostochka A. V., Woodall D. R. List edge and list total colourings of multigraphs // J. Combin. Theory (B). 1997. V. 71, N 2. P. 184–204.
     
  24. Ferencová 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.
     
  25. Jendrol’ S., Maceková M. Describing short paths in plane graphs of girth at least 5 // Discrete Math. 2015. V. 338, N 2. P. 149–158.
     
  26. Dvořá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.
     
  27. Borodin O. V., Ivanova A. O. Describing edges in normal plane maps having no adjacent 3-faces // Sib. Electron. Math. Rep. 2024. V. 21, N 1. P. 495–500.

Работа первого автора поддержана Министерством науки и высшего образования России (проект FWNF-2022-0017). Работа второго автора поддержана Министерством науки и высшего образования России, грант FSRG-2023-0025.

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

E-mail: brdnoleg@math.nsc.ru

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

E-mail: shmgnanna@mail.ru

Статья поступила 4 июня 2025 г.
После доработки — 4 июня 2025 г.
Принята к публикации 15 августа 2025 г.