An asymptotic result for the path partition conjecture
The electronic journal of combinatorics, Tome 12 (2005)
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).$
@article{10_37236_1945,
author = {Marietjie Frick and Ingo Schiermeyer},
title = {An asymptotic result for the path partition conjecture},
journal = {The electronic journal of combinatorics},
year = {2005},
volume = {12},
doi = {10.37236/1945},
zbl = {1075.05046},
url = {http://geodesic.mathdoc.fr/articles/10.37236/1945/}
}
Marietjie Frick; Ingo Schiermeyer. An asymptotic result for the path partition conjecture. The electronic journal of combinatorics, Tome 12 (2005). doi: 10.37236/1945
Cité par Sources :