On vertex-disjoint paths in regular graphs

Abstract

Let $c\in (0,1]$ be a real number and let $n$ be a sufficiently large integer. We prove that every $n$-vertex $cn$-regular graph $G$ contains a collection of $\lfloor 1/c\rfloor$ paths whose union covers all but at most $o(n)$ vertices of $G$. The constant $\lfloor 1/c\rfloor$ is best possible when $1/c\notin \mathbb{N}$ and off by $1$ otherwise. Moreover, if in addition $G$ is bipartite, then the number of paths can be reduced to $\lfloor 1/(2c)\rfloor$, which is best possible.

arXiv comment4 pages