Name
Title | ||
|---|---|---|
On the complexity of the selective graph coloring problem in some special classes of graphs. |
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1016/j.tcs.2013.04.018 | Theoretical Computer Science |
Keywords | DocType | Volume |
Computational complexity,Approximation algorithms,PTAS,Scheduling,Bipartite graphs,Split graphs,Complete q-partite graphs,Clustering | Journal | 540 |
ISSN | Citations | PageRank |
0304-3975 | 8 | 0.52 |
References | Authors | |
11 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marc Demange | 1 | 267 | 29.78 |
| Jérôme Monnot | 2 | 512 | 55.74 |
| Petrica C. Pop | 3 | 183 | 27.86 |
| Bernard Ries | 4 | 176 | 28.68 |