# Equivalent Colorings of Graphs

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.

• 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. May 10, 2018 at 17:07

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.