Kernels by rainbow paths in arc-colored tournaments.

For an arc-colored digraph D , define its kernel by rainbow paths to be a set S of vertices such that (i) no two vertices of S are connected by a rainbow path in D , and (ii) every vertex outside S can reach S by a rainbow path in D. In this paper, we first show that it is NP-complete to decide whether an arc-colored tournament has a kernel by rainbow paths, where a tournament is an orientation of a complete graph. In addition, we show that every arc-colored n -vertex tournament with all its strongly connected k -vertex subtournaments, 3 ⩽ k ⩽ n , colored with at least k − 1 colors has a kernel by rainbow paths. [ABSTRACT FROM AUTHOR]