Abstract: Пусть wk максимум минимальной суммы степеней вершин (веса) в k-вершинных цепях (k-цепях) 3-многогранников. Очевидно, что каждый 3многогранник содержит вершину степени не больше 5, так что w1 ≤ 5. Ещев 1955 г. Коциг доказал, что w2 ≤ 13 (т. е. найдется ребро веса не больше 13), причем оценка точна. В 1993 г. Андо, Ивасаки и Канеко доказали, что w3 ≤ 21, и эта оценка также неулучшаема ввиду конструкции Йендроля, найденной в 1997 г. В 1997 г. О. В. Бородин уточнил этот результат, показав, что w3 ≤ 18 верно для всех 3многогранников с w2 ≥ 7, но для 3-многогранников с w2 ≥ 8 имеет место более сильная оценка w3 ≤ 17, причем неулучшаемость 18 была подтверждена О. В. Бородиным и др. в 2013 г, а неулучшаемость 17 была известна давно. За последние три десятилетия большое число работ было посвящено задачам раскраски и структурным задачам на плоских графах, разреженных в том или ином смысле. В данной статье рассматриваются 3-многогранники без смежных 3-циклов, т. е. не имеющие хордальных 4-циклов (иначе говоря, без K4 − e). Известно, что для таких 3-многогранников w1 ≤ 4 и, более того, w2 ≤ 9, где обе оценки точны (Бородин, 1992). Доказано, что всякий 3-многогранник без хордальных 4-циклов содержит 3-цепь веса не более 15, т. е. w3 ≤ 15, и эта оценка неулучшаема.

Cite: Бородин О.В. , Иванова А.О.
Легкие 3-цепи в 3-многогранниках без смежных 3-граней
Сибирский математический журнал. 2024. Т.65. №2. С.249-257. DOI: 10.33048/smzh.2024.65.202 РИНЦ

Translated: Borodin O.V. , Ivanova A.O.
Light 3-Paths in 3-Polytopes without Adjacent Triangles
Siberian Mathematical Journal. 2024. V.65. N2. P.257-264. DOI: 10.1134/S0037446624020022 WOS Scopus РИНЦ РИНЦ OpenAlex

Dates:

Submitted:	Oct 17, 2023
Accepted:	Nov 28, 2023
Published print:	Mar 25, 2024
Published online:	Mar 25, 2024

Identifiers:

Elibrary:

65623353

Citing: Пока нет цитирований

Altmetrics: