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

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.