Дискретная математика и математическая кибернетика
Путевая разбиваемость планарных графов с ограничениями на расположение коротких циклов
А. Н. Глебов 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