|
Дискретная математика и математическая кибернетика
Путевая разбиваемость планарных графов с ограничениями на расположение коротких циклов
А. Н. Глебов 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.
Поступила 15 ноября 2020 г., опубликована 15 сентября 2021 г.
Образец цитирования:
А. Н. Глебов, “Путевая разбиваемость планарных графов с ограничениями на расположение коротких циклов”, Сиб. электрон. матем. изв., 18:2 (2021), 975–984
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/semr1414 https://www.mathnet.ru/rus/semr/v18/i2/p975
|
|