Эта публикация цитируется в
1 статье
Дискретная математика и математическая кибернетика
Путевая разбиваемость планарных графов обхвата 4 без смежных коротких циклов
А. Н. Глебов,
Д. Ж. Замбалаева Sobolev Institute of Mathematics,
pr. Koptyuga, 4,
630090, Novosibirsk, Russia
Аннотация:
A graph
$G$ is
$(a,b)$-partitionable for positive intergers
$a,b$ if its vertex set can be partitioned into subsets
$V_1,V_2$ such that the induced subgraph
$G[V_1]$ contains no path on
$a+1$ vertices and the induced subgraph
$G[V_2]$ contains no path on
$b+1$ vertices. A graph
$G$ is
$\tau$-partitionable if it is
$(a,b)$-partitionable for every pair
$a,b$ such that
$a+b$ is the number of vertices in the longest path of
$G$. In 1981, Lovász and Mihók posed the following Path Partition Conjecture: every graph is
$\tau$-partitionable. In 2007, we proved the conjecture for planar graphs of girth at least 5. The aim of this paper is to improve this result by showing that every triangle-free planar graph, where cycles of length 4 are not adjacent to cycles of length 4 and 5, is
$\tau$-partitionable.
Ключевые слова:
graph, planar graph, girth, triangle-free graph, path partition,
$\tau$-partitionable graph, path partition conjecture.
УДК:
519.172.2,
519.174
MSC: 05C10,
05C15,
05C70 Поступила 30 ноября 2017 г., опубликована
21 сентября 2018 г.
DOI:
10.17377/semi.2018.15.087