Menu
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(\langle A \rangle) \leq a \) and \( \tau(\langle B \rangle) \leq 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.