Rainbow Paths in Properly Edge-Colored Regular Graphs

Definitions and mathematical statement

Let $k$ be a positive integer. A simple graph $G=(V,E)$ has no loops or multiple edges and is $k$-regular if every vertex is incident with exactly $k$ edges. A proper $k$-edge-colouring is a map $c:E\to\{1,\ldots,k\}$ such that distinct edges sharing a vertex receive different colours. A path of length $\ell$ consists of distinct vertices $v_0,\ldots,v_\ell$ with $\{v_{i-1},v_i\}\in E$ for $1\le i\le\ell$. It is rainbow if these $\ell$ edges have pairwise distinct colours.

The supplied conjecture asks whether every simple $k$-regular graph equipped with a proper $k$-edge-colouring contains a rainbow path of length $k-1$. Explicitly, for each such coloured graph, must there exist distinct vertices $v_0,\ldots,v_{k-1}$ satisfying \[ \{v_{i-1},v_i\}\in E\quad(1\le i\le k-1), \qquad c(\{v_{i-1},v_i\})\ne c(\{v_{j-1},v_j\}) \quad(1\le i<j\le k-1)? \] For $k=1$, this means a path consisting of one vertex and no edges.

Unresolved scope qualifications. The source does not explicitly specify finiteness, nonemptiness, or the range of $k$. The formulation above uses $k\ge1$, since $k=0$ would request a negative path length. It requires a nonempty graph: if the empty graph is admitted as vacuously $k$-regular and properly $k$-edge-coloured, the assertion fails. Whether the intended quantification is over finite nonempty graphs or also infinite nonempty graphs requires confirmation from the source.

Short English statement

The conjecture asks whether a simple $k$-regular graph with a proper colouring of its edges using $k$ colours always has a path with $k-1$ edges whose colours are all different. The intended graph class and parameter range need confirmation. The supplied record labels the problem partially solved; that label and its literature assessment have not been independently verified.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30004002$, title: Rainbow Paths in Properly Edge-Colored Regular Graphs; exact source problem code: catalogue entry. The record gives proposed year 2018 and does not name a proposer. Its corrected_verified statement label is supplied registry metadata, not an independent verification here.
• Supplied report citation: Combinatorial Optimization (2019), Oberwolfach Reports, DOI 10.4171/owr/2018/50, pp. 2969--3023. https://doi.org/10.4171/owr/2018/50. The record describes this provenance as workshop open-problem discussions collected from Oberwolfach Reports.
• Supplied literature reference: Towards Graham's Rearrangement Conjecture via Rainbow Paths. https://arxiv.org/abs/2503.01825.
• Supplied literature reference: Rainbow Paths in Edge-Coloured Regular Graphs. https://homepages.cwi.nl/~lex/files/rainbowpath.pdf.
• Literature assessment dated exactly 2026-08-21: supplied dated curation, not independently verified. It labels the problem partially solved and reports that the conjecture is proved for bounded degree and asymptotically in full generality, stating that every properly edge-coloured $d$-regular graph has a rainbow path of length $(1-o(1))d$, while the exact $d-1$ assertion remains unresolved. The supplied background calls this a dated literature triage derived from OWR curation and requests independent verification of time-sensitive status and cited claims. The degree range and precise asymptotic hypotheses are not supplied.