1
$\begingroup$

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]

enter image description here

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.

$\endgroup$

2 Answers 2

1
$\begingroup$

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
$\endgroup$
1
$\begingroup$
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]
  ]
$\endgroup$
1
  • $\begingroup$ It is also nice. $\endgroup$
    – licheng
    Commented Feb 21 at 10:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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