An Asymptotic Result for the Path Partition Conjecture

Abstract

The detour order of a graph $G$, denoted by $\tau \left( G\right) ,$ is the order of a longest path in $G.$ A partition of the vertex set of $G$ into two sets, $A$ and $B,$ such that $\tau (\left\langle A\right\rangle )\leq a$ and $\tau (\left\langle B\right\rangle )\leq b$ is called an $(a,b)$-partition of $G$. If $G$ has an $(a,b)$-partition for every pair $(a,b)$ of positive integers such that $a+b=\tau (G),$ then we say that $G$ is $\tau $-partitionable. The Path Partition Conjecture (PPC), which was discussed by Lovász and Mihók in 1981 in Szeged, is that every graph is $\tau $-partitionable. It is known that a graph $G$ of order $n$ and detour order $\tau =n-p$ is $\tau $-partitionable if $p=0,1.$ We show that this is also true for $p=2,3,$ and for all $p\geq 4$ provided that $n\geq p(10p-3).$