Demange, Marc Monnot, Jérôme Pop, Petrica Ries, Bernard 2014 In this paper, we consider the selective graph coloring problem. Given an integer k ≥ 1 and a graph G = (V, E) with a partition V1, . . . , Vp of V, it consists in deciding whether there exists a set V∗ in G such that |V∗ ∩ Vi| = 1 for all i ∈ {1, . . . , p}, and such that the graph induced by V∗ is k-colorable. We investigate the complexity status of this problem in various classes of graphs. application/pdf https://folia.unifr.ch/global/documents/325860 https://folia.unifr.ch/documents/325860/files/SELCOL_copy.pdf eng info:eu-repo/semantics/altIdentifier/doi/10.1016/j.tcs.2013.04.018 info:eu-repo/semantics/altIdentifier/issn/0304-3975 info:eu-repo/semantics/openAccess Rights reserved Theoretical Computer Science. - Elsevier BV. - 2014, vol. 540-541, p. 89-102 Computational complexity Approximation algorithms PTAS Scheduling Bipartite graphs Split graphs Complete q-partite graphs Clustering info:eu-repo/classification/udc/004 On the complexity of the selective graph coloring problem in some special classes of graphs http://purl.org/coar/resource_type/c_6501