I have been given a graph with n nodes. Now, I have to color every node of this graph by k colors, number from 0 to k-1. Now, there is a rule.

For a node $x$ with adjacent nodes $y_1 , y_2, y_3, y_4,... y_m$, $color(x)=(color(y_1)+color(y_2)+color(y_3)+...+color(y_m)) \pmod k $

where $color(a)$ indicates a color number from 0 to k-1. I have to find number of ways I can color the whole graph.

My approach to the problem was simple. I was constructing a $n*n$ matrix for n nodes in graph with equations like $col(x)-col(y_1)-col(y_2)-col(y_3)...-col(y_m)$. And trying to find number of all zero rows, which will provide us number of free variable. Is my approach correct?

  • 1
    $\begingroup$ You ask if your approach is correct. What do you think? What happens when you try your approach? Have you tried it on some small examples to see if you get the right answer? Have you tried to prove that it is correct? $\endgroup$
    – D.W.
    Nov 10 '13 at 6:14
  • $\begingroup$ My assumption is, for a series of dependent variables, I can only assign one set of value which will solve every equation. For some small example I am getting right answer. But when I am submitting the code to judge I am getting Wrong Answer. $\endgroup$ Nov 10 '13 at 8:08
  • 1
    $\begingroup$ (1) I suggest you edit your question to add a small example, and also edit your question to add your attempt at a proof/justification that your algorithm is correct. (2) Are you familiar with the concept of linear dependence or independence of vectors? with the rank of a matrix? Can you see any way in which those concepts might be relevant? Can you see any way in which you could have two rows that are dependent but not all-zero? (3) Do adjacent vertices have to have different colors? Have you taken that into account? $\endgroup$
    – D.W.
    Nov 10 '13 at 19:18

As, no good solutions were given and my research else where proved to be helpful, I am answering my own question. The main idea of the solution is correct.

The number of independent variables controls the total possible way of coloring but the matrix construction is little different.

The matrix will look like this for the following graph.

A graph with 4 nodes $\{1,2,3,4\}$ and 4 edges $\{(1,2),(2,3),(3,4),(4,1)\}$ provides us the equations,

$col_1 \equiv (col_2+col_4)\mod k$

$col_2 \equiv (col_1+col_3)\mod k$

$col_3 \equiv (col_2+col_4)\mod k$

$col_4 \equiv (col_1+col_3)\mod k$

Providing us equations like,

$(col_1 -col_2-col_4)\mod k \equiv 0$

$(col_2 -col_1-col_3)\mod k \equiv 0$

$(col_3 -col_2-col_4)\mod k \equiv 0$

$(col_4 -col_1-col_3)\mod k \equiv 0$

We form matrix like this for these equations:

$$ \begin{bmatrix} 1 & k-1 & 0 & k-1\\ k-1 &1 & k-1 & 0\\ 0 &k-1 & 1 & k-1\\ k-1 &0 & k-1 & 1\\ \end{bmatrix} $$

Not to mention for every step of Gaussian elimination we have to use mod operation, if any number is negative take the equivalent positive mod.

Then, for every independent variable we can assign a value from 0 to (k-1) and get solution for every of these equations. If number of independent variables is $x$ then the answer will be $k^x$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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