Path Partitionable Graphs

Abstract

The detour order of a graph $G$, denoted $\tau (G)$, is the order of a longest path in $G$. A partition $(A,B)$ of $V(G)$ such that $\tau (⟨A⟩)\le a$ and $\tau (⟨B⟩)\le b$ is called an $(a,b)$-partition of $G$. A graph $G$ is called $\tau$-\textit{partitionable} if $G$ has an $(a,b)$-partition for every pair $(a,b)$ of positive integers such that $a+b=\tau (G)$.

The well-known Path Partition Conjecture states that every graph is $\tau$-partitionable. Motivated by the recent result of Dunbar and Frick [6] that if every $2$-connected graph is $\tau$-partitionable, then every graph is $\tau$-partitionable, we show that the Path Partition Conjecture is true for a large family of $2$-connected graphs with certain ear-decompositions. Also, we show that a family of $2$-edge-connected graphs with certain ear-decompositions is $\tau$-partitionable.