|
Discrete mathematics and mathematical cybernetics
Path partitioning planar graphs with restrictions on short cycles
A. N. Glebov Sobolev Institute of Mathematics, 4, Koptyuga ave., Novosibirsk, 630090, Russia
Abstract:
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.
Keywords:
graph, planar graph, girth, path partition, $\tau$-partitionable graph, Path Partition Conjecture.
Received November 15, 2020, published September 15, 2021
Citation:
A. N. Glebov, “Path partitioning planar graphs with restrictions on short cycles”, Sib. Èlektron. Mat. Izv., 18:2 (2021), 975–984
Linking options:
https://www.mathnet.ru/eng/semr1414 https://www.mathnet.ru/eng/semr/v18/i2/p975
|
Statistics & downloads: |
Abstract page: | 79 | Full-text PDF : | 21 | References: | 16 |
|