3
$\begingroup$

Consider a graph and a set of ordered colors ${\cal C} = \{1,2,\cdots,C\}$. I want to color each node $i$ with a color $c_i\in{\cal C}$ so as to maximize the minimum color difference between two neighbor nodes. That is, let two neighbor nodes $i$ and $j$ colored $c_i$ and $c_j$, let $\delta_{ij}\triangleq |c_i-c_j|$, I want to find a distributed coloring algorithm that maximises the minimum of $\delta_{ij}$ of the graph. The difference between this problem with the classical distributed coloring problem is the ordered color set.

$\endgroup$
1
  • 1
    $\begingroup$ This is a specialization of the graph T-coloring problem, which is said to have application to [frequency assignment](www.inets.rwth-aachen.de/pub/Frequency_allocation_for_WLAN.pdf) problems. $\endgroup$
    – bof
    Nov 22, 2014 at 13:00

1 Answer 1

1
$\begingroup$

This is NP-hard, since we can reduce the classical distributed coloring problem to this problem (if the minimum of $\delta_{ij}$ of the graph is at least $1$, then it is $C$-colorable.

$\endgroup$

Your Answer

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

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