Lima, Paloma T. ;
van Leeuwen, Erik Jan ;
van der Wegen, Marieke
Algorithms for the Rainbow Vertex Coloring Problem on Graph Classes
Abstract
Given a vertexcolored graph, we say a path is a rainbow vertex path if all its internal vertices have distinct colors. The graph is rainbow vertexconnected 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 vertexconnected. This problem is known to be NPcomplete even in very restricted scenarios, and very few efficient algorithms are known for it. In this work, we give polynomialtime 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 polynomialtime solvability results for split strongly chordal graphs by showing that, for any fixed p ≥ 3 both variants of the problem become NPcomplete when restricted to split (S₃,…,S_p)free graphs, where S_q denotes the qsun graph.
BibTeX  Entry
@InProceedings{lima_et_al:LIPIcs:2020:12733,
author = {Paloma T. Lima and Erik Jan van Leeuwen and Marieke van der Wegen},
title = {{Algorithms for the Rainbow Vertex Coloring Problem on Graph Classes}},
booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
pages = {63:163:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771597},
ISSN = {18688969},
year = {2020},
volume = {170},
editor = {Javier Esparza and Daniel Kr{\'a}ľ},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12733},
URN = {urn:nbn:de:0030drops127331},
doi = {10.4230/LIPIcs.MFCS.2020.63},
annote = {Keywords: rainbow vertex coloring, permutation graphs, powers of trees}
}
18.08.2020
Keywords: 

rainbow vertex coloring, permutation graphs, powers of trees 
Seminar: 

45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Issue date: 

2020 
Date of publication: 

18.08.2020 