On the fine-grained complexity of rainbow coloring

Łukasz Kowalik, Juho Lauri, Arkadiusz Socała

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…