I haven't been able to find whether this problem has been studied: we are given a graph $G$ and an ordered list of $k$ colors $L = [\ell_1, \cdots, \ell_k]$. Additionally, we are given a positive integer $s \le k-1$.

The decision question is whether $G$ can be properly colored such that every pair of adjacent vertices will receive two colors within distance $s$ in the list (i.e., if the two colors are $\ell_i$ and $\ell_j$, then $|i-j| \le s$).

This is of course equivalent to the standard coloring problem when $s = k-1$. Would be interested in both exact and approximation algorithms (if known).

  • $\begingroup$ You're looking for a homomorphism from your graph into the graph on $[k]$ in which $i,j$ are connected if $0 < |i-j| \leq s$. $\endgroup$ – Yuval Filmus Oct 26 '20 at 20:07

Your Answer

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

Browse other questions tagged or ask your own question.