Consider a finite set of colors and a given an unweighted graph with the following properties:

1) Graph is connected.

2) All vertices of the graph has a color in the given set of colors.

3) No two adjacent vertices have the same color.

Define a flip as the following: change the color of a given vertex V AND all reachable vertices from V only if those reachable vertices have the same original color with V (that is, all vertices that have a path to V consisting of only vertices of the same colors have their color changed).

What's the optimal strategy to find the smallest amount of flip in order so that all vertices have the same color?

For example the following graph needs 2 flips: R | \ B B | | Y Y First flip is from vertex red to color blue: B | \ B B | | Y Y Then flip the top blue vertex and change it to yellow, triggering all the other blue vertices to yellow: Y | \ Y Y | | Y Y

I was thinking of exploring all possibilities by try flipping all vertices, but this seems to be inefficient as I might have to explore all the flipping possibilities before finding the optimal one.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.