论文标题
彩虹顶点着色问题的算法在图课上
Algorithms for the rainbow vertex coloring problem on graph classes
论文作者
论文摘要
给定顶点颜色的图，我们说如果其所有内部顶点都具有不同的颜色，则一条路径是彩虹顶点路径。如果其每对顶点之间都有彩虹顶点路径，则该图是彩虹顶点连接的。在彩虹顶点着色（RVC）问题中，我们想决定是否可以将给定图的顶点涂上最多$ k $颜色的颜色，从而使图成为彩虹顶点连接。即使在非常有限的场景中，也已知该问题是NP完整的，而且很少有有效的算法以此而闻名。在这项工作中，我们为RVC提供了多项式时间算法，在置换图，树的幂和划分的弦图上。后类的算法也适用于问题的强烈变体，在该问题的强烈变体中，每个顶点对之间的彩虹顶点路径必须是最短的路径。我们通过表明，对于任何固定的$ p \ geq 3 $，当问题的两个变体都限制为split $（s_3，\ ldots，s_p）$ - 免费图形，其中$ s_q $表示$ q $ -sunsun图时，我们通过证明任何固定的$ p \ geq 3 $ confully split spline conteral graphs的多项式时间可溶性结果补充了多项式时时间的可溶性结果。
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.
