Описание 3-граней в 3-многогранниках без смежных треугольников

Описание 3-граней в 3-многогранниках без смежных треугольников

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

УДК 519.17 
DOI: 10.33048/smzh.2025.66.102

Аннотация:

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

В этой статье рассмотрены наиболее плотные среди неплотных $3$-многогранников, а именно не содержащие смежных $3$-циклов. О. В. Бородин в 1996 г. доказал, что такие $3$-многогранники содержат вершину степени не более $4$ и, более того, ребро с суммой степеней концевых вершин не более $9$, где обе оценки неулучшаемы. 

Через $d(v)$ обозначим степень вершины $v$. Ребро $e = xy$ в $3$-многограннике есть $(i, j)$-ребро, если $d(x) \le i$ и $d(y) \le j$. Известный $(3, 5; 4, 4)$-полуправильный многогранник отвечает плоской четыреангуляции, в которой каждое ребро соединяет $3$-вершину с $5$-вершиной. В частности, этот многогранник не содержит $3$-циклов. 

Недавно О. В. Бородин и А. О. Иванова доказали, что любой $3$-многогранник, не содержащий ни смежных $3$-циклов, ни $(3, 5)$-ребер, содержит $3$-грань с суммой степеней инцидентных вершин (весом) не более $16$, причем эта оценка неулучшаема. 

$3$-Грань $f = (x, y, z)$ называется $(i, j, k)$-гранью или гранью типа $(i, j, k)$, если $d(x) \le i$, $d(y) \le j$ и $d(z) \le k$. Цель данной работы — доказать, что существуют ровно два точных описания типов $3$-граней в $3$-многогранниках без смежных $3$-граней при указанном выше необходимом условии отсутствия $(3, 5)$-ребер, а именно: {$(3, 6, 7) \lor (4, 4, 7)$} и {$(4, 6, 7)$}. 

Отсюда следует, что имеет место единственное точное описание $3$-граней в $3$-многогранниках без $3$-вершин, не содержащих смежных $3$-граней: {$(4, 4, 7)$}.

Литература:
  1. Dvo$\check{r}$á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.
     
  2. 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.
     
  3. Borodin O. V. Structural properties of plane graphs without adjacent triangles and an application to 3-colorings // J. Graph Theory. 1996. V. 21. P. 183–186.
     
  4. Бородин О. В. Усиление теоремы Лебега о строении младших граней в выпуклых многогранниках // Дискрет. анализ и исслед. операций. 2002. Т. 9, № 3. С. 29–39.
     
  5. Borodin O. V., Hartke S. G., Ivanova A. O., Kostochka A. V., West D. B. (5, 2)-Coloring of sparse graphs // Sib. Elektron. Mat. Izv. 2008. V. 5. P. 417–426.
     
  6. Borodin O. V., Ivanova A. O. Planar graphs without 4-cycles adjacent to 3-cycles are list vertex 2-arborable // J. Graph Theory. 2009. V. 62, N 3. P. 234–240.
     
  7. 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.
     
  8. Borodin O. V., Ivanova A. O., Vasil’eva E. I. A Steinberg-like approach to describing faces in 3-polytopes // Graphs and Combinatorics. 2017. V. 33, N 1. P. 63–71.
     
  9. 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.
     
  10. Hudak P., Macekov´a 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.
     
  11. Jendrol’ S. A structural property of convex 3-polytopes // Geom. Dedicata. 1997. V. 68. P. 91–99.
     
  12. Borodin O. V. Colorings of plane graphs: a survey // Discrete Math. 2013. V. 313, N 4. P. 517–539.
     
  13. 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.
     
  14. 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.
     
  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. 030051.
     
  16. Borodin O. V. More about the weight of edges in planar graphs // Tatra Mountains Math. Publ. 1996. V. 9. P. 11–14.
     
  17. Borodin O. V., Ivanova A. O. Light 3-faces in 3-polytopes without adjacent triangles // Discrete Math. 2025. V. 348, N 1. 114299.

Работа О. В. Бородина поддержана Министерством науки и высшего образования России (проект 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

Статья поступила 30 октября 2024 г.
После доработки — 30 октября 2024 г.
Принята к публикации 25 декабря 2024 г.