Call two proper graph colorings equivalent if one can be obtained from the other by a permutation of the colors. In other words, they are the "same" coloring.

I'm interested in finding proper non-equivalent colorings. Of course, the decision problem of determining whether or not there is such a non-equivalent coloring given one is NP-complete.

Are there FPT, approximation, etc. algorithms for finding such a coloring if one exists? I am currently running a randomized greedy coloring algorithm, which does often succeed in finding a proper coloring - however, I am unsure of when it actually produces a non-isomorphic one.

If it is helpful, I'm working with graphs which are essentially $k$-trees.

  • $\begingroup$ You didn't say anything about these colourings being minimal, so: For any set $X$ of vertices having the same colour, you can produce a non-equivalent colouring for every partition of $X$: Assign one block in the partition the original colour, and every other block gets a completely fresh colour not used anywhere else. $\endgroup$ May 10, 2018 at 17:07

1 Answer 1


Many existing heuristics for graph coloring can work even if you specify the colors of a few vertices. So, here is one plausible algorithm you could use:

We are given an existing coloring $C$. Pick two vertices $v,w$ randomly. We are going to assign colors for $v,w$ (in the new coloring), leave the other vertices unassigned, and use some existing graph coloring heuristic to extend this to a coloring for the whole graph. If $C(v)=C(w)$, assign $v,w$ two different colors in the new coloring (any two, it doesn't matter which two colors you use). If $C(v)\ne C(w)$, assign $v,w$ the same color in the new coloring (any color, it doesn't matter which you pick). Then extend this to a coloring for the new graph.

If this finds a coloring, then you're guaranteed that the new coloring will be non-equivalent to the old one. Moreover, if there exists a non-equivalent coloring, you're guaranteed to be able to find it with at most polynomially many invocations of this procedure. In particular, if $C'$ is non-equivalent, there must exist some pair of vertices $v,w$ where $C(v)=C(w)$ and $C'(v) \ne C'(w)$, or where $C(v) \ne C(w)$ and $C'(v) = C'(w)$. Therefore, if you repeat the above procedure for all pairs $v,w$ of vertices, at least one of those iterations should find a new non-equivalent coloring.

So, this might be one reasonable approach, if you want to find a new non-equivalent coloring once. On the other hand, if you are given $m$ existing colorings and want to find a $m+1$st non-equivalent coloring, that looks more complicated.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.