  For an integer $q\ge 2$ and an even integer $d$, consider the graph obtained
from a large complete $q$-ary tree by connecting with an edge any two vertices
at distance exactly $d$ in the tree. This graph has clique number $q+1$, and
the purpose of this short note is to prove that its chromatic number is
$\Theta\big(\tfrac{d \log q}{\log d}\big)$. It was not known that the chromatic
number of this graph grows with $d$. As a simple corollary of our result, we
give a negative answer to a problem of van den Heuvel and Naserasr, asking
whether there is a constant $C$ such that for any odd integer $d$, any planar
graph can be colored with at most $C$ colors such that any pair of vertices at
distance exactly $d$ have distinct colors. Finally, we study interval coloring
of trees (where vertices at distance at least $d$ and at most $cd$, for some
real $c>1$, must be assigned distinct colors), giving a sharp upper bound in
the case of bounded degree trees.
