RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирские электронные математические известия // Архив

Сиб. электрон. матем. изв., 2021, том 18, выпуск 2, страницы 975–984 (Mi semr1414)

Дискретная математика и математическая кибернетика

Путевая разбиваемость планарных графов с ограничениями на расположение коротких циклов

А. Н. Глебов

Sobolev Institute of Mathematics, 4, Koptyuga ave., Novosibirsk, 630090, Russia

Аннотация: Let $a$ and $b$ be positive intergers. An $(a,b)$-partition of a graph is a partition of its vertex set into two subsets so that in the subgraph induced by the first subset each path contains at most $a$ vertices while in the subgraph induced by the second subset each path contains at most $b$ vertices. A graph $G$ is $\tau$-partitionable if it has an $(a,b)$-partition for any pair $a,b$ such that $a+b$ equals to the number of vertices in the longest path in $G$. The celebrated Path Partition Conjecture of Lovász and Mihók ($1981$) states that every graph is $\tau$-partitionable. In $2018$, Glebov and Zambalaeva proved the Conjecture for triangle-free planar graphs where cycles of length $4$ have no common edges with cycles of length $4$ and $5$. The purpose of this paper is to generalize this result by proving that every planar graph in which cycles of length $4$ to $7$ have no chords while $3$-cycles have no common vertices with cycles of length $3$ and $4$ is $\tau$-partitionable.

Ключевые слова: graph, planar graph, girth, path partition, $\tau$-partitionable graph, Path Partition Conjecture.

УДК: 519.172.2, 519.174

MSC: 05C10, 05C15, 05C70

Поступила 15 ноября 2020 г., опубликована 15 сентября 2021 г.

DOI: 10.33048/semi.2021.18.073



Реферативные базы данных:


© МИАН, 2024