set of colors S = {0,1,2,.....,n-1}
some vertices of graph has been assigned a color from set S
Now if its possible to color the graph using color from S so that no two adjacent vertices have same color?
Thanks
Coloring a Partially Colored Graph
Moderator: Board moderators
So you have n colors?
Since the maximum degree of a vertex is n-1, this is always possible. (Actually, if you have n vertices, you can just color all of them a different color).
If you're asking about the case where n is just the number of colors, and not the number of vertices in the graph, the problem is NP-complete, because you can reduce the NP-complete problem of vertex coloring to solutions of this problem.
Since the maximum degree of a vertex is n-1, this is always possible. (Actually, if you have n vertices, you can just color all of them a different color).
If you're asking about the case where n is just the number of colors, and not the number of vertices in the graph, the problem is NP-complete, because you can reduce the NP-complete problem of vertex coloring to solutions of this problem.