7
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – anomaly
    Jan 14, 2019 at 4:12
  • 1
    $\begingroup$ @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. $\endgroup$ Jan 14, 2019 at 4:16
  • $\begingroup$ @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. $\endgroup$ Jan 14, 2019 at 4:21
  • 1
    $\begingroup$ @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. $\endgroup$ Jan 14, 2019 at 4:23
  • $\begingroup$ @MishaLavrov: Is the swap in the connected component of $G$ itself, or just in some induced subgraph? I was assuming the former. $\endgroup$
    – anomaly
    Jan 14, 2019 at 4:26

1 Answer 1

2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – DVD
    Jan 17, 2019 at 1:31
  • $\begingroup$ 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. $\endgroup$
    – DVD
    Jan 17, 2019 at 1:48
  • 1
    $\begingroup$ My intuition is that this sort of thing is unlikely to produce a complete invariant, but likely to make the needed counterexamples more complicated. $\endgroup$ Jan 17, 2019 at 3:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .