For integer $1\le k\le n$, let ${\overline H}_n^k$ denote the complement of
the $k$-th power of the Hamming graph on the vertex set ${\mathbb
F}_2^n$; that is, two vectors from ${\mathbb F}_2^n$ are adjacent in
${\overline H}_n^k$ whenever they differ in $k+1$ coordinates at least.
What is the chromatic number of this graph?

Assuming for simplicity that $k$ is even, the [Kneser graph][1]
$G_{n,k/2+1}$ is a subgraph of ${\overline H}_n^k$. As a result,
  $$ \chi({\overline H}_n^k) \ge \chi(G_{n,k/2+1})=n-k. $$
Improving upon this estimate (for $k$ close to $n$) would yield an
improved bound for the number of Hamming spheres, needed to cover the
whole space ${\mathbb F}_2^n$ (see [this MO post][2]).

[1]: http://en.wikipedia.org/wiki/Kneser_graph
[2]: http://mathoverflow.net/questions/99893/can-you-cover-the-boolean-cube-0-1n-with-o1-hamming-balls-each-of-radius-n-2/99906#99906