3
$\begingroup$

Given a $n \times m$ grid, define a valid coloring as mapping from the grid cells to a set of $k$ available colors such that no two adjacent cells have the same color. Cells are considered as adjacent if they share a side. How many valid colorings are there? Let $f(n, m, k)$ be the answer.

I search for a way to compute $f(n, m, k)$ fast, primarily in terms of time complexity. However, a polynomial-time solution is not required.

This problem was proposed in Codesprint 5 at HackerRank with constraints $1 \le n,m \le 8$ and $k \le 10^9$. However, I am not asking for this particular case, so it does not matter so much. It is worth mentioning there is a discussion on TopCoder, but I do not get it after several readings.

Approaches. I present my thoughts as following. First, we may explicitly enumerate all colorings. This works only on very small instances, because the number of colorings is growing exponentially. In order to see this, consider an $1 \times m$ grid and $k = 3$ colors. The first cell may be colored in $3$ ways and each following cell in $2$ ways, which yields $f(1, m, 3) = 3 \cdot 2^{m - 1}$.

Let's consider $n = 2$. If $m = 1$, we simply get $f(2, 1, 3) = 6$. Assume, we know $f(2, m, 3)$ for some $m \in \mathbb{N}$. Let $X$ and $Y$ be the colors in the rightmost / last column for an abritrary valid coloring of $2 \times m$ grid. In $(m + 1)^{th}$ column, there are $2$ colors for the top cell $(Y$ and the third color, say $Z$). Distinguish between two cases.

Case #1: Top cell has color $Y$. Then, our bottom cell can get color $X$ or color $Z$. There are two possible choices.

Case #2: Top cell has color $Z$. Then, our bottom cell must have color $X$.

Altogether, there are $3$ possibilities for the next step, i.e. $f(2, m + 1, 3) = 3 \cdot f(2, m, 3)$. Using our base case and solving the recurrence, the result comes out to be $f(2, m, 3) = 2 \cdot 3^m$.

These counting arguments get more complicated for larger values of $n$, even for $n = 3$ I do not find an explicit formula. In the original problem, there are significantly more colors than cells. It should be sufficient to consider colorings with exactly $1, 2, \dots, mn$ colors (let $a_{i}$ be the respective answers) and compute $\displaystyle \sum_{i = 1}^{mn} \binom{k}{i} a_{i}$. Therefore, don't worry too much about this step.

Hints and approaches are appreciated as well as solutions and references.

Improve this question
$\endgroup$
6
  • $\begingroup$ Note that this is an open problem for general graphs: citeseerx.ist.psu.edu/viewdoc/… $\endgroup$
    – Stella Biderman
    Nov 6, 2017 at 4:48
  • $\begingroup$ Thank you for reference. I updated the question remarking that not necessarily a polynomial-time solution is required or meant by "compute fast". $\endgroup$
    – neutron-byte
    Nov 6, 2017 at 11:56
  • $\begingroup$ @StellaBiderman That article seems to be about the somewhat different problem of counting colourings up to renaming of the colours (i.e., red-blue-red is equivalent to blue-red-blue, but different from red-blue-green). $\endgroup$
    – David Richerby
    Nov 6, 2017 at 13:31
  • $\begingroup$ @DavidRicherby But they’re the same thing up to a multiplicative factor of $k!$ $\endgroup$
    – Stella Biderman
    Nov 6, 2017 at 13:54
  • $\begingroup$ @StellaBiderman Suppose you wish to count $k$-colourings. Each equivalence class of colourings that use exactly $q<k$ different colours corresponds to $\binom{k}{q}$ different colourings, so the number of (at-most) $k$-colourings is $\sum_{q=1}^k \binom{k}{q}N_q$, where $N_q$ is the number of equivalence classes of exactly-$q$ colourings. You can't just multiply everything by $k!$. $\endgroup$
    – David Richerby
    Nov 6, 2017 at 14:03

1 Answer 1

Reset to default
2
$\begingroup$

For every graph $G$ on $n$ vertices there is a degree $n$ polynomial $\chi_G$ such that $\chi_G(k)$ is the number of valid $k$-colorings of the graph. This polynomial is known as the chromatic polynomial, and can be found in exponential time. The easiest solution to the programming challenge is to precompute the chromatic polynomials. For example, denoting the $n \times m$ grid by $G(n,m)$, we have $$ \begin{align*} \chi_{G(1,1)} &= x \\ \chi_{G(1,2)} &= x^2 - x \\ \chi_{G(2,2)} &= x^4 - 4x^3 + 6x^2 - 3x \\ \chi_{G(1,3)} &= x^3 - 2x^2 + x \\ \chi_{G(2,3)} &= x^6 - 7x^5 + 21x^4 - 33x^3 + 27x^2 - 9x \\ \chi_{G(3,3)} &= x^9 - 12x^8 + 66x^7 - 216x^6 + 459x^5 - 648x^4 + 594x^3 - 323x^2 + 79x \end{align*} $$

Improve this answer
$\endgroup$
2
  • $\begingroup$ How to compute the chromatic polynomial? I think, one must know the number of valid colorings for $k = 1, k = 2, \dots, k = mn$ colors to uniquely determine the polynomial of degree $mn$. But with this knowledge, one can just apply the sum formula at the end of my question and get the same result with less work, i.e. with the work of simple brute-force. Is there a still exponential but more efficient way to precompute the chromatic polynomial? $\endgroup$
    – neutron-byte
    Nov 6, 2017 at 16:36
  • $\begingroup$ There is extensive literature about computing the chromatic polynomial. You can start by reading the Wikipedia article. $\endgroup$
    – Yuval Filmus
    Nov 6, 2017 at 16:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.