Путевая разбиваемость планарных графов с ограничениями на расположение коротких циклов
Ключевые слова:
граф, планарный граф, обхват, путевое разбиение, $\tau$-разбиваемый граф, гипотеза о путевой разбиваемости.Аннотация
Пусть a и b - положительные целые числа. Путевым (a,b)-разбиением графа называется такое разбиение множества его вершин на два подможества, что в подграфе, порожденном первым подмножеством, любая простая цепь содержит не более a вершин, а в подграфе, порожденном вторым подмножеством, любая простая цепь содержит не более b вершин. Граф G называется $\tau$-разбиваемым,
если он имеет (a,b)-разбиение для любых таких a,b, что a+b равняется числу вершин в наибольшей простой цепи графа G. Известная гипотеза Ловаса и Михока о путевой разбиваемости (1981) гласит, что любой граф является $\tau$-разбиваемым. В 2018 г. Глебов и Замбалаева доказали эту гипотезу для планарных графов без циклов длины 3, в которых циклы длины 4 не имеют общих ребер с циклами длины 4 и 5. Целью настоящей статьи является усиление данного результата. а именно, доказательство того, что любой планарный граф, в котором циклы длины от 4 до 7 не имеют хорд, а циклы длины 3 не имеют общих вершин с циклами длины 3 и 4, является $\tau$-разбиваемым.
