Thumbnail - Request a copy

On the complexity of the selective graph coloring problem in some special classes of graphs

Ries, Bernard; Pop, Petrica; Monnot, Jérôme; Demange, Marc (2014), On the complexity of the selective graph coloring problem in some special classes of graphs, Theoretical Computer Science, 540-541, p. 89-102. 10.1016/j.tcs.2013.04.018

Type
Article accepté pour publication ou publié
Date
2014
Journal name
Theoretical Computer Science
Volume
540-541
Publisher
Elsevier
Pages
89-102
Publication identifier
Metadata
Show full item record
Author(s)
Ries, Bernard
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Pop, Petrica
Université Technique de Cluj-Napoca
Monnot, Jérôme cc
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Demange, Marc
ESSEC Business School
Abstract (EN)
In this paper, we consider the selective graph coloring problem. Given an integer k≥1k≥1 and a graph G=(V,E)G=(V,E) with a partition V1,…,VpV1,…,Vp of VV, it consists in deciding whether there exists a set V∗V∗ in GG such that ∣V∗∩Vi∣=1∣V∗∩Vi∣=1 for all i∈{1,…,p}i∈{1,…,p}, and such that the graph induced by V∗V∗ is kk-colorable. We investigate the complexity status of this problem in various classes of graphs.
Subjects / Keywords
Clustering; Complete qq-partite graphs; Split graphs; Bipartite graphs; Scheduling; PTAS; Approximation algorithms; Computational complexity