I have the following dummy problem:
Claim - There exists $N$ such that for $n > N$, if $G_n$ be a connected directed vertex-transitive graph with $n$ vertices, then there exists a set $S$ of paths on $G_n$, such that $$\bigcup_{P \in S} P = V(G_n),$$ $$|S| < \frac{n}{\log(n)^4},$$ $$\sum_{P \in S} |P| < \left( 1+ \frac{1}{\log(n)^4}\right)n.$$
I am interested as my research involves trying to prove a similar claim with additional restrictions on $P$, but I am not sure how to begin attacking such a problem.
One idea I’ve thought might be useful is a Theorem of Gallai and Milgram:
If a digraph $G$ has independence number $\alpha$, then $G$ can be partitioned into $\alpha$ paths.
