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

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.

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

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]
]

• It is also nice. Commented Feb 21 at 10:49