1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ @ParclyTaxel Consider a group G acting on a set C, where the G contains permutations for corners and the C contains all the colorings. The set of orbits of (coloring c in) C under the action of G form a partition of C, two colorings x and y are equivalent if and only if their orbits are the same. $\endgroup$
    – chansey
    Sep 24, 2022 at 16:29
  • $\begingroup$ @ParclyTaxel For example, suppose we want to color the four corners of a square with red and blue, the coloring equivalence means if allowed geometric motion onto itself, the ways to color are partitioned into parts in such a way that two colorings in the same part are regarded as the same. In this example, there are 16 ways to color if we don't consider rotating and flipping, but there are 6 ways to color, if we consider them. $\endgroup$
    – chansey
    Sep 24, 2022 at 16:31
  • $\begingroup$ @ParclyTaxel Graph isomorphisms may be interesting, but here I just consider symmetric motion, which Burnside can be applied (but as I said in the question, Burnside doesn't consider "adjacent vertices with different colors"). $\endgroup$
    – chansey
    Sep 24, 2022 at 16:34
  • $\begingroup$ What distinction are you drawing between graph automorphisms and "symmetric motion"? Even to apply Burnside's theorem to count improper $k$-colorings of a graph, you'd need to know the automorphism group first. $\endgroup$ Sep 24, 2022 at 16:40
  • $\begingroup$ @MishaLavrov Sorry, I'm not familiar with graph theory. Brualdi's book doesn't connect graph automorphism and "symmetric motion", but now I think they are the same! Thanks. For this question, I'm just curious if Burnside's Theorem and Pólya's Counting can be applied to "adjacent vertices with different colors". $\endgroup$
    – chansey
    Sep 24, 2022 at 16:48

1 Answer 1

2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ To compute |X^g| by first define a graph Γ/g, then get its chromatic polynomial. Very clever solution, thanks! $\endgroup$
    – chansey
    Sep 24, 2022 at 17:37
  • 1
    $\begingroup$ This OCP algorithm was implemented in Maple at the following MSE link. For reference, these are called orbital chromatic polynomials. $\endgroup$ Sep 24, 2022 at 18:36

You must log in to answer this question.

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