Coloring a Partially Colored Graph

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am

Coloring a Partially Colored Graph

Post by rushel »

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?


New poster
Posts: 35
Joined: Mon Dec 10, 2001 2:00 am
Location: Singapore; Cambridge, MA

Post by chrismoh »

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.

Post Reply

Return to “Algorithms”