In this work we deal with a vertex coloring problem where we are given an undirected graph G=(V,E) and a set of colors C={1,2,…k}. With each edge e∈E is associated a weight and with each vertex v∈V a subset ∅≠Cv⊆C. A coloring of the vertices is feasible if each vertex v is colored with a color of Cv. A coloring uniquely defines a subset E′⊆E of edges having different colored endpoints. The problem of finding a feasible coloring which defines a minimum weight E′ is, in general, NP-complete. In this work an implicit enumeration scheme for finding such an optimal coloring is presented. Upper and lower bounds evaluations are based on a O(|V|k) combinatorial algorithm for the special case of trees and cacti.