1
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

As, no good solutions were given and my research else where, proved to be helpful. So, 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$

$\endgroup$

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.