All tight descriptions of 3-paths in plane graphs with girth at least 9

Valerii Anatol evich Aksenov, Oleg Veniaminovich Borodin, Anna Olegovna Ivanova

Результат исследования: Научные публикации в периодических изданияхстатьярецензирование

4 Цитирования (Scopus)


Lebesgue (1940) proved that every plane graph with minimum degree δ at least 3 and girth g at least 5 has a path on three vertices (3-path) of degree 3 each. A description is tight if no its parameter can be strengthened, and no triplet dropped. Borodin et al. (2013) gave a tight description of 3-paths in plane graphs with δ ≥ 3 and g ≥ 3, and another tight description was given by Borodin, Ivanova and Kostochka in 2017. Borodin and Ivanova (2015) gave seven tight descriptions of 3-paths when δ ≥ 3 and g ≥ 4. Furthermore, they proved that this set of tight descriptions is complete, which was a result of a new type in the structural theory of plane graphs. Also, they characterized (2018) all oneterm tight descriptions if δ ≥ 3 and g ≥ 3. The problem of producing all tight descriptions for g ≥ 3 remains widely open even for δ ≥ 3. Recently, several tight descriptions of 3-paths were obtained for plane graphs with δ = 2 and g ≥ 4 by Jendrol', Maceková, Montassier, and Soták, four of which descriptions are for g ≥ 9. In this paper, we prove ten new tight descriptions of 3-paths for δ = 2 and g ≥ 9 and show that no other tight descriptions exist.

Язык оригиналаанглийский
Страницы (с-по)1174-1181
Число страниц8
ЖурналSiberian Electronic Mathematical Reports
СостояниеОпубликовано - 2018
Опубликовано для внешнего пользованияДа

Предметные области OECD FOS+WOS