Maximum colorful cliques in vertex-colored graphs - Laboratoire Interdisciplinaire des Sciences du Numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2018

Maximum colorful cliques in vertex-colored graphs

Résumé

In 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.
Fichier non déposé

Dates et versions

hal-01827893 , version 1 (02-07-2018)

Identifiants

Citer

Giuseppe F Italiano, Yannis Manoussakis, Kim Thang Nguyen, Hong-Phong Pham. Maximum colorful cliques in vertex-colored graphs. COCOON 2018 - 24th International Computing and Combinatorics Conference, Jul 2018, Qingdao, China. pp.480-491, ⟨10.1007/978-3-319-94776-1_40⟩. ⟨hal-01827893⟩
236 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More