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

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

• The number of vertex-colorings of $G$ using exactly $n$ colors can be derived from the chromatic polynomial of $G$, and (at least in the connected case) $C_n(G)$ is just that modulo an extra factor of $1/n!$. The chromatic polynomial is not a complete graph invariant. Commented Jan 14, 2019 at 4:12
• @anomaly Why would $C_n(G)$ be the number of $n$-colorings divided by $n!$? There are colorings which are equivalent, but are not obtained from each other just by permuting the colors. Commented Jan 14, 2019 at 4:16
• @MishaLavrov: I thought equivalence is a type of permutation, at least within a connected component. The OP said to swap the colors a and b. The only restriction seems to be that $a$ and $b$ have to share an edge to allow the permutation to be legal. Commented Jan 14, 2019 at 4:21
• @CheerfulParsnip As I understand it, we only swap the colors $a$ and $b$ on the connected component of the subgraph induced by those colors. So the colors $a$ and $b$ get swapped in parts of the graph, but not others, even if the graph as a whole is connected. If we take the other interpretation, the question is trivial. Commented Jan 14, 2019 at 4:23
• @MishaLavrov: Is the swap in the connected component of $G$ itself, or just in some induced subgraph? I was assuming the former. Commented Jan 14, 2019 at 4:26

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

(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$$.

• What if we attach its diameter to every equivalence class of colorings for the invariant? That is, $D_n^k$ = the maximum number of swaps between $k$th equivalent coloring class of $n$ colors. Then I get, that $D_4^1(bowtie)=1$ and $D_4^1(kite)=2$, so $D$ distinguishes them. Could this modified invariant be complete?
– DVD
Commented Jan 17, 2019 at 1:31
• It may be useful to add the transformation between colorings that may decrease the number of colors, that is if we have a node with neighbors of few different colors then its color may be changed. For planar graphs it garantees that every coloring is equivalent to a five coloring, please see en.wikipedia.org/wiki/Five_color_theorem.
– DVD
Commented Jan 17, 2019 at 1:48
• My intuition is that this sort of thing is unlikely to produce a complete invariant, but likely to make the needed counterexamples more complicated. Commented Jan 17, 2019 at 3:43