17 citations · 50 across the 13 of their papers we have counts for
Showing 2016Show all
3 papers · 1 filter
cs.CC2016
Complexity of Rainbow Vertex Connectivity Problems for Restricted Graph Classes
Juho Lauri
A path in a vertex-colored graph is \emph{vertex rainbow} if all of its internal vertices have a distinct color. The graph is said to be \emph{rainbow vertex connected} if…
math.CO2016★ 1 cited
The square of the 9-hypercube is 14-colorable
Juho Lauri
The -hypercube, denoted by , has a vertex for each bit string of length with two vertices adjacent whenever their Hamming distance is one. The minimum number of colors…
cs.DS2016
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 colors so that every pair of vertices is connected by a rainbow path, i.e., a path with…