Maximum colorful cliques in vertex-colored graphs

International audienceIn this paper we study the problem of finding a maximum colorful clique in vertex-colored graphs. Specifically, given a graph with colored vertices, we wish to find a clique containing the maximum number of colors. Note that this problem is harder than the maximum clique problem, which can be obtained as a special case when each vertex has a different color. In this paper we aim to give a dichotomy overview on the complexity of the maximum colorful clique problem. We first show that the problem is NP-hard even for several cases where the maximum clique problem is easy, such as complement graphs of bipartite permutation graphs, complement graphs of bipartite convex graphs, and unit disk graphs, and also for properly vertex-colored graphs. Next, we provide a XP parameterized algorithm and polynomial-time algorithms for classes of complement graphs of bipartite chain graphs, complete multipartite graphs and complement graphs of cycle graphs, which are our main contributions