Sharp Rainbow Path Covers in Dense and Complete Multipartite Graphs

A path in a properly edge-colored graph is rainbow if its edges have pairwise distinct colors. For a proper edge-coloring $c$ of a graph $G$, let $\mathrm{rpc}(G,c)$ be the minimum number of rainbow paths needed to cover $E(G)$, and let $\mathrm{rpc}(G)$ be the maximum of $\mathrm{rpc}(G,c)$ over all proper edge-colorings of $G$. We prove that, for every fixed $0<\alpha <1$, every properly edge-colored $n$-vertex graph with minimum degree at least $\alpha n$ satisfies $\mathrm{rpc}(G,c)\le (1+o(1))n\mathrm{/}2$, where the coefficient $1\mathrm{/}2$ is best possible. We also determine $\mathrm{rpc}(G)$ asymptotically for every complete multipartite graph. If $G=K_{n_1,\dots ,n_r}$ has order $n$ and largest and smallest part sizes $M$ and $s$, respectively, then, uniformly over all choices of the number and sizes of the parts, $\mathrm{rpc}(G)=(1+o(1))\max \{\min \{\lfloor n\mathrm{/}2\rfloor ,n-M\},(n-s)\mathrm{/}2\}$. The proof combines pseudorandom packings of globally rainbow linear forests with a decomposition into dense parts and prescribed avoidance for arbitrary dense graphs, and with reserved connectors and a direct dominant-part argument for complete multipartite graphs.