Sharp Rainbow Path Covers in Dense and Complete Multipartite Graphs
Abstract
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 rpc(G,c) be the minimum number of rainbow paths needed to cover E(G), and let rpc(G) be the maximum of 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 rpc(G,c)≤(1+o(1))n/2, where the coefficient 1/2 is best possible. We also determine rpc(G) asymptotically for every complete multipartite graph. If G=Kn1,…,nr 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, rpc(G)=(1+o(1))max{min{⌊ n/2⌋,n−M},(n−s)/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.
Related
- The Game Chromatic Number of Complete Multipartite Graphs with Singletons and Large Parts
- An e-positive classification for complete multipartite graphs
- A new infinite family of covers of complete graphs that admit a half-transitive action of a Suzuki simple group
- Edge complexity of complete bipartite and complete multipartite graphs
- Enumerative geometry of conics and double covers on projective complete intersections
BibTeX
@misc{liu2026sharp,
title = {{Sharp Rainbow Path Covers in Dense and Complete Multipartite Graphs}},
author = {Xiao-Chuan Liu and Boyan Xu and Xu Yang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.18740},
eprint = {2609.18740},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.18740},
}
RIS
TY - UNPB
TI - Sharp Rainbow Path Covers in Dense and Complete Multipartite Graphs
AU - Xiao-Chuan Liu
AU - Boyan Xu
AU - Xu Yang
PY - 2026
DA - 2026/09/16
PB - arXiv
DO - 10.48550/arxiv.2609.18740
UR - https://arxiv.org/abs/2609.18740
AB - 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 rpc(G,c) be the minimum number of rainbow paths needed to cover E(G), and let rpc(G) be the maximum of 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 rpc(G,c)≤(1+o(1))n/2, where the coefficient 1/2 is best possible. We also determine rpc(G) asymptotically for every complete multipartite graph. If G=K_n_1,…,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, rpc(G)=(1+o(1))max{min{⌊ n/2⌋,n−M},(n−s)/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.
ER -