Is there any systematic way to compute the number of nonequivalent colorings for a graph (adjacent vertices with different colors)

coloringcombinatoricsgraph theory

I am reading Brualdi's book Introductory Combinatorics (self-learning).

In the section 12.1,

the author introduced chromatic polynomial, which can calculate the number of k colorings of G. It also introduced an algorithm for computing the chromatic polynomial of any graph.

Note that (1) the chromatic polynomial requires all the adjacent vertices to be assigned different colors (good) (2) the result of the chromatic polynomial includes all equivalent ways (bad, I want nonequivalent ways!).

In the section 14.2,

the author introduced Burnside's Theorem, which can calculate the number of k colorings of G in nonequivalent ways. However, its condition is too loose, it doesn't require adjacent vertices be assigned different colors.

In the section 14.3,

the author introduced Pólya's Counting Formula, which can specify the number of times each color is used. However, like Burnside's Theorem, it still doesn't require adjacent vertices to be assigned different colors.

My question is that

Is there any systematic way to compute the number of nonequivalent colorings for a graph (e.g. a cube or a regular 5-gon), but adjacent vertices must be assigned different colors?

Thanks.

Best Answer

(Terminology: we say that a $k$-coloring of a graph $\Gamma$ is proper if adjacent vertices get different colors; two $k$-colorings are isomorphic if there is an automorphism of $\Gamma$ which takes one coloring to the other.)

Burnside's lemma $$ |X/G| = \frac1{|G|} \sum_{g\in G}|X^g| $$ applies to counting the number of orbits of any set $X$ acted on by a group $G$; it can already be used to count proper colorings. If $G$ is a group acting on a graph $\Gamma$, if we want $|X/G|$ to be the number of non-isomorphic proper colorings of $\Gamma$, just take $X$ to be the set of proper colorings of $\Gamma$ (counted by the chromatic polynomial evaluated at $k$.) The trick, however, is to evaluate $|X^g|$: the number of proper colorings fixed by a group element $g$.

Given a graph $\Gamma$ and a group element $g$ which permutes the vertices of $\Gamma$, a coloring is fixed by $g$ if, for every vertex $v$, the colors of $v, gv, g^2v, \dots$ are all the same. The way to compute $|X^g|$ in this case is as follows:

  1. If there is any vertex $v$ which is adjacent to $g^k v$ for any power $k$, then $|X^g| =0$, because there is no proper coloring in which $v$ and $g^k v$ are given the same color.
  2. Otherwise, we can define a smaller graph $\Gamma/g$ by taking a quotient: for every vertex $v$, identify $v$ with $gv$. (To enforce that these vertices get the same color, just make them the same vertex!) Then the number of proper $k$-colorings of $\Gamma$ fixed by $g$ is equal to the number of proper $k$-colorings of $\Gamma/g$, which can be found by computing its chromatic polynomial.

For a simple example, suppose we want to count the non-isomorphic $k$-colorings of the graph below:

    a
   / \
  /   \
b ----- c
  \   /
   \ /
    d

The automorphism group has four elements: the identity $e$, the horizontal flip $h$ (which swaps $b$ and $c$), the vertical flip $v$ (which swaps $a$ and $d$), and their product $hv$.

The number of proper $k$-colorings fixed by $e$ is just the chromatic polynomial of the graph: $k(k-1)(k-2)^2$.

The number of proper $k$-colorings fixed by $h$ is $0$: if a coloring is fixed by $h$, then $b$ and $c$ get the same color, so it is not proper. Similarly, the number of proper $k$-colorings fixed by $hv$ is $0$.

For the number of proper $k$-colorings fixed by $v$, we want to take the graph quotient where we identify vertices $a$ and $d$ (since they must get the same color). This gives us the graph

    ad
   /  \
  /    \
b ------ c

whose chromatic polynomial is $k(k-1)(k-2)$.

Now Burnside's lemma tells us that the number of non-isomorphic proper $k$-colorings is $$ \frac14(k(k-1)(k-2)^2 + k(k-1)(k-2)). $$

Related Question