Let $n$ be a natural number and assume for a start that $n$ is divisible by $3$. Let $\sigma$ be a permutation of the set $\{1,2,\ldots, n\}$. I want to partition the vector $S=(\sigma(1),\sigma(2),\ldots, \sigma(n))$ into three vectors $(a_1,\ldots, a_{n/3})=A$, $(b_1,\ldots, b_{n/3})=B$ and $(c_1,\ldots, c_{n/3})=C$ of equal length. Because this is boring, I impose some restrictions. First, I don't want to have consecutive numbers in one vector, so for example $a_i=3$, $a_j=4$ for some $i,j$ is not allowed. Second, I require that for all $i$, $a_i=\sigma(j)$ implies $|3i-j|\leq k$, where $k$ is some constant independent of $n$ (and the same for $B$ and $C$).

Consider the following example. If $\sigma$ is the identical permutation, I choose $A=(1,4,7,\ldots)$, $B=(2,5,8,\ldots)$, $C=(3,6,9,\ldots)$. Then for each vector every pair of components has distance $2$, and $A$, $B$ and $C$ have "uniform density", because I roughly "chose every third number".

The question is, whether there is $k$ such that the above construction is possible for all $n$ and $\sigma$.

The second question is, if partitioning into $3$ vectors fails, does it work for $4$ instead of $3$ or an even larger number?

NOTE: I set the graph-theory tag, because using graph theory seems like a reasonable approach to me.