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