TY - GEN

T1 - Algorithms for the rainbow vertex coloring problem on graph classes

AU - Lima, Paloma T.

AU - van Leeuwen, Erik Jan

AU - van der Wegen, Marieke

PY - 2020/8/1

Y1 - 2020/8/1

N2 - 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 ≥ 3 both variants of the problem become NP-complete when restricted to split (S3, . . ., Sp)-free graphs, where Sq denotes the q-sun graph.

AB - 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 ≥ 3 both variants of the problem become NP-complete when restricted to split (S3, . . ., Sp)-free graphs, where Sq denotes the q-sun graph.

KW - Permutation graphs

KW - Powers of trees

KW - Rainbow vertex coloring

UR - http://www.scopus.com/inward/record.url?scp=85090510986&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.MFCS.2020.63

DO - 10.4230/LIPIcs.MFCS.2020.63

M3 - Conference contribution

AN - SCOPUS:85090510986

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

SP - 63:1--63:13

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

A2 - Esparza, Javier

A2 - Kral, Daniel

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020

Y2 - 25 August 2020 through 26 August 2020

ER -