Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs

Given a graph with colors on its vertices, a path is called a rainbow vertex path if all its internal vertices have distinct colors. We say that the graph is rainbow vertex-connected if there is a rainbow vertex path between every pair of its vertices. We study the problem of deciding whether the vertices of a given graph can be colored with at most $k$ colors so that the graph becomes rainbow vertex-connected. Although edge-colorings have been studied extensively under similar constraints, there are significantly fewer results on the vertex variant that we consider. In particular, its complexity on structured graph classes was explicitly posed as an open question. We show that the problem remains NP-complete even on bipartite apex graphs and on split graphs. The former can be seen as a first step in the direction of studying the complexity of rainbow coloring on sparse graphs, an open problem which has attracted attention but limited progress. In terms of approximation, we show that the minimum number of colors required to rainbow vertex-connect an $n$-vertex bipartite graph nor an $n$-vertex split graph can be approximated within a factor of $n^{1/2-eps}$ for any $eps > 0$ unless $P = NP$. Furthermore, we prove that this is tight by giving a polynomial-time algorithm for general graphs with an approximation guarantee of $O(n^{1/2})$. To complement the negative results, we show that bipartite permutation graphs, interval graphs, and block graphs can be rainbow vertex-connected optimally in polynomial time.