\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac2{{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Marietjie Frick and Ingo Schiermeyer}
%
%
\medskip
\noindent
%
%
{\bf An Asymptotic Result for the Path Partition Conjecture}
%
%
\vskip 5mm
\noindent
%
%
%
%
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)${\em %
-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.{\em \ }The Path Partition Conjecture (PPC), which was
discussed by Lov\'{a}sz and Mih\'{o}k in 1981 in Szeged, is that every graph
is $\tau $-{\em 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).$

\bye

.
