A new graph invariant? The maximum number of non-equivalent colorings with $n$ colors.

coloringgraph theoryinvarianceinvariant-theoryplanar-graphs

Consider (proper) coloring of a finite graph $G$ with exactly $n$ colors and the following coloring transformation: choose an edge of the graph with the end nodes of colors $a$ and $b$ and swap the colors $a$ and $b$ in the connected component of the graph, containing the edge and colored with the two colors. The result is new (proper) coloring of the graph. Lets call two colorings equivalent if there is a sequence of the swaps taking one graph coloring into another. Let $C_n(G)$ be a maximum number of non-equivalent colorings of the graph $G$ with $n$ colors (number of equivalence classes).

QUESTIONS:

  • Is $C_n(G)$ a new graph invariant or it can be calculated from the chromatic polynomial of the graph $G$?
  • Is there efficient way to calculate $C_n(G)$?
  • Could $C_n(G)$ be a complete graph invariant, considering it for all natural numbers $n$?

NOTE:

For the non-triviality and the origin of $C_n(G)$, please, see On the four and five color theorems

Best Answer

The sequence $C_n(G)$ is not a complete graph invariant. It fails to distinguish the bowtie graph (left) from the kite graph (right):

https://hog.grinvin.org/ViewGraphInfo.action?id=776 https://hog.grinvin.org/ViewGraphInfo.action?id=782

(I picked these two graphs to try based on their use in this paper; Richard P. Stanley: A symmetric function generalization of the chromatic polynomial of a graph; DOI: 10.1006/aima.1995.1020.)

For both graphs, $C_3(G) = C_4(G) = C_5(G) = 1$ while $C_n(G) = 0$ for all other $n$.

Related Question