# Coloring the $k$-deletion graph “constructively”

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