Linear rainbow path cover of edge-colored graphs

Problem 4 · arXiv:2301.08707

arXiv Problem high confidence— first stated 2023-10-10

Authors: Marthe Bonamy, Fábio Botler, François Dross, Tássio Naia, Jozef Skokan

Status open high confidence

Problem 4 of arXiv:2301.08707 asks whether every properly edge-colored graph G admits O(|V(G)|) rainbow paths that cover E(G). The authors note that a version with trails instead of paths is already verifiable, but the path case remains open. No follow-up paper specifically addressing this problem was found in the literature through May 2026.

Reviewer notes. No follow-up found in 5 web calls. The paper was published in Advances in Combinatorics (2023). A related follow-up arXiv:2407.02102 by Botler et al. extends the separating-system theme to cycles and K_4 subdivisions, but does not address Problem 4. The problem is recent (2023) and the absence of follow-up is expected; open with high confidence.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Problem. Does every properly edge-colored graph $G$ admit $O(|V(G)|)$ rainbow paths that cover $E(G)$?

Context

This question arose from initial attempts to solve Conjecture 1; a rainbow path is a path containing no two edges of the same color. An affirmative answer would yield an alternative proof of Conjecture 1 via a path decomposition argument, and the authors note that a version with 'trails' replacing 'paths' can already be verified.

Source paper

Separating the edges of a graph by a linear number of paths
Marthe Bonamy, Fábio Botler, François Dross, Tássio Naia, Jozef Skokan · 2023-10-10
https://arxiv.org/abs/2301.08707 PDF source