Algorithms for the rainbow vertex coloring problem on graph classes

Paloma T. Lima, Erik Jan van Leeuwen, Marieke van der Wegen

Given a vertex-colored graph, we say a path is a rainbow vertex path if all its internal vertices have distinct colors. The graph is rainbow vertex-connected if there is a rainbow…