On the Fine-Grained Complexity of Rainbow Coloring
On the Fine-Grained Complexity of Rainbow Coloring
The Rainbow $k$-Coloring problem asks whether the edges of a given graph can be colored in $k$ colors so that every pair of vertices is connected by a rainbow path, i.e., a path with all edges of different colors. Our main result states that for any $k\ge 2$, there is …