On the complexity of the selective graph coloring problem in some special classes of graphs
BP2-STS
- Demange, Marc ESSEC Business School and LAMSADE UMR 7243, France
- Monnot, Jérôme CNRS, LAMSADE UMR 7243, France
- Pop, Petrica Technical University of Cluj-Napoca, North University Center of Baia Mare, Romania
- Ries, Bernard ORCID Université de Fribourg, Switzerland
- 2014
Published in:
- 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
English
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.
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.
- Faculty
- Faculté des sciences économiques et sociales et du management
- Department
- Département d'informatique
- Language
-
- English
- Classification
- Computer science and technology
- License
- Rights reserved
- Open access status
- green
- Identifiers
-
- DOI 10.1016/j.tcs.2013.04.018
- ISSN 0304-3975
- Persistent URL
- https://folia.unifr.ch/unifr/documents/325860
Statistics
Document views: 19
File downloads:
- SELCOL_copy.pdf: 34