Algorithms for the rainbow vertex coloring problem on graph classes
Preprint
Abstract
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 vertex path between every pair of its vertices. In the Rainbow Vertex Coloring (RVC) problem we want to decide whether the vertices of a given graph can be colored with at most $k$ colors so that the graph becomes rainbow vertex-connected. This problem is known to be NP-complete even in very restricted scenarios, and very few efficient algorithms are known for it. In this work, we give polynomial-time algorithms for RVC on permutation graphs, powers of trees and split strongly chordal graphs. The algorithm for the latter class also works for the strong variant of the problem, where the rainbow vertex paths between each vertex pair must be shortest paths. We complement the polynomial-time solvability results for split strongly chordal graphs by showing that, for any fixed $p\geq 3$ both variants of the problem become NP-complete when restricted to split $(S_3,\ldots,S_p)$-free graphs, where $S_q$ denotes the $q$-sun graph.
Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- On the complexity of rainbow coloring problemsDiscrete Applied Mathematics, 2018
- A Survey on the Computational Complexity of Coloring Graphs with Forbidden SubgraphsJournal of Graph Theory, 2016
- Linear-Time Algorithms for Tree Root ProblemsAlgorithmica, 2013
- Further hardness results on the rainbow vertex-connection number of graphsTheoretical Computer Science, 2013
- The complexity of determining the rainbow vertex-connection of a graphTheoretical Computer Science, 2011
- The rainbow connection of a graph is (at most) reciprocal to its minimum degreeJournal of Graph Theory, 2009
- An Optimal Algorithm to Solve the All-Pairs Shortest Paths Problem on Permutation GraphsJournal of Mathematical Modelling and Algorithms, 2003
- Modular decomposition and transitive orientationDiscrete Mathematics, 1999