For $n,k\ge 1$, we define the graph $D_{n,k}$ to have vertex set $\{0,1\}^n$, with distinct $x,y$ being adjacent if $LCS(x,y)\ge n-k$.
My question is: fixing $k>1$, does there exist some $C=C_k$ and a coloring algorithm $\chi$ for the set of binary strings, such that:
- for each $n\ge 1$, $\chi|_{\{0,1\}^n}$ is a proper coloring of $D_{n,k}$ which takes at most $Cn^C$ values,
- for $x \in\{0,1\}^n$, $\chi(x)$ can be computed using $O(n^C)$ time and space.
I am aware of such an algorithm for $k=1$. Here, for $x\in \{0,1\}^n$, one takes $\chi(x)$ to be $\sum_{i =1}^n i x_i \pmod{n+1}$ (it’s not immediately obvious it works but the proof is fairly simple). But for $k>1$ I do not know of anything.
Further remarks: Noticing $D_{n,k}$ has maximum degree $O_k(n^{2k})$, we non-constructively see that $\chi(D_{n,k}) = O_k(n^{2k})$. Asymptotically no better bound is known for $k>1$, though recently a preprint proved that $D_{n,k}$ contains independent sets of size $\Omega_k(\log n/n^{2k})$ (https://arxiv.org/abs/2209.11882).
