How to determine if two colorings of a graph are the same?

Question

A coloring of a graph $G$ with vertex set $V$ is the partitioning of $V$ into so-called color classes so that no two vertices of the same class are adjacent. A $k$-coloring contains exactly $k$ color classes.

We shall think of a $k$-coloring of $G$ as a map $\psi: V \rightarrow\{1,2, \ldots, k\}$ such that $\psi^{-1}(i), i=1,2, \ldots, k$, are the color classes of $G$. Naturally two maps, $\psi_1$ and $\psi_2$, represent the same $k$-coloring if and only if $\psi_1=\psi_2 \circ \pi$ for some permutation $\pi$ of $\{1,2, \ldots, k\}$.

My goal is: given a graph with two $k$-colorings, I want to determine if they are the same. I am unsure which function to use. Ultimately, the final objective is to determine how many different $k$-colorings the graph has in total.

For example,

g1 = Graph[{a \[UndirectedEdge] b, b \[UndirectedEdge] c, 
   c \[UndirectedEdge] d, d \[UndirectedEdge] a, 
   a \[UndirectedEdge] c}, VertexLabels -> "Name"]
vertexColorings = ResourceFunction["FindProperColorings"][g1, 3]

We obtained six $3$-colorings, and are they the same? How to represent permutations of vertices in the definition using a function in Mathematica?

{{1, 2, 3, 2}, {1, 3, 2, 3}, {2, 1, 3, 1}, {2, 3, 1, 3}, {3, 1, 2, 1}, {3, 2, 1, 2}}

---

After that, we may obtain all uniquely colorable simple graphs up to 10 vertices. See https://oeis.org/A369223 corresponding to their counts.

Additional information: The chromatic number of $G$, denoted by $\chi(G)$, is the minimal $k$ for which $G$ has a $k$-coloring. A graph with exactly one $k$-coloring is called uniquely $k$-colorable. It is obvious that if $G$ is uniquely $k$-colorable then $\chi(G)=k$ or $n$, so we shall say simply that $G$ is uniquely colorable if it is uniquely $\chi(G)$ colorable.

Answer 1

Let's think of $k$-colourings are partitioning of the vertex set into $k$ classes. We can represent these classes as a list of lists. Then all we need to do is canonicalize the list-of-lists representation using sorting (Sort[Sort /@ partitions]) and compare directly with ===.

IGraph/M has function to convert between a "membership representation" (i.e. each vertex is assigned a value) and a partition representation (i.e. disjoint groups of vertices).

For example, let our vertices be a, b, and c. We assign colour x to a, b and colour y to c. Then you can use:

In[158]:= IGMembershipToPartitions[{a, b, c}, {x, x, y}]
Out[158]= {{a, b}, {c}}

This function is well-tested and performant.

In most use cases we'll have integers for both vertex names and colour names, but I wanted to demonstrate that the function works with other expressions as well.

You can define some helpers,

canonicalizeColoring[vertexList_?ListQ][colors_] := 
 Sort[Sort /@ IGMembershipToPartitions[vertexList, colors]]

canonicalizeColoring[graph_?GraphQ] := 
 canonicalizeColoring[VertexList[graph]]

Then use them as

In[164]:= g = CycleGraph[3];

In[165]:= 
canonicalizeColoring[g][{1, 1, 2}] === canonicalizeColoring[g][{2, 2, 1}]

Out[165]= True

Answer 2

properColoringPartitions[g_Graph, k_Integer] := 
 With[{vxs = VertexList[g],cols = ResourceFunction["FindProperColorings"][g, k]},
  Keys@GroupBy[{#,Values@GroupBy[Thread[vxs -> #], Last -> First]} & /@ cols,Last -> First]
  ]