# “Close” Graph Coloring?

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).

• 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$. – Yuval Filmus Oct 26 '20 at 20:07