{"id":"arxiv/2609.18740","url":"https://arxiv.org/abs/2609.18740","tags":["math.CO"],"score":0,"title":"Sharp Rainbow Path Covers in Dense and Complete Multipartite Graphs","domain":"math.CO","source":"arxiv","authors":["Xiao-Chuan Liu","Boyan Xu","Xu Yang"],"reviews":0,"subject":"math.CO","summary":"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 $\\operatorname{rpc}(G,c)$ be the minimum number of rainbow paths needed to cover $E(G)$, and let $\\operatorname{rpc}(G)$ be the maximum of $\\operatorname{rpc}(G,c)$ over all proper edge-colorings of $G$. We prove that, for every fixed $0<α<1$, every properly edge-colored $n$-vertex graph with minimum degree at least $αn$ satisfies $\\operatorname{rpc}(G,c)\\leq(1+o(1))n/2$, where the coefficient $1/2$ is best possible. We also determine…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-16","reactions":{}}