  A proper $k$-coloring of a graph $G=(V,E)$ is a function $c: V(G)\to
\{1,\ldots,k\}$ such that $c(u)\neq c(v)$, for every $uv\in E(G)$. The
chromatic number $\chi(G)$ is the minimum $k$ such that there exists a proper
$k$-coloring of $G$. Given a spanning subgraph $H$ of $G$, a $q$-backbone
$k$-coloring of $(G,H)$ is a proper $k$-coloring $c$ of $V(G)$ such that
$\lvert c(u)-c(v)\rvert \ge q$, for every edge $uv\in E(H)$. The $q$-backbone
chromatic number $BBC_q(G,H)$ is the smallest $k$ for which there exists a
$q$-backbone $k$-coloring of $(G,H)$. In this work, we show that every
connected graph $G$ has a generating tree $T$ such that $BBC_q(G,T) =
\max\{\chi(G),\left\lceil\frac{\chi(G)}{2}\right\rceil+q\}$, and that this
value is the best possible.
  As a direct consequence, we get that every connected graph $G$ has a spanning
tree $T$ for which $BBC_2(G,T)=\chi(G)$, if $\chi(G)\ge 4$, or
$BBC_2(G,T)=\chi(G)+1$, otherwise. Thus, by applying the Four Color Theorem, we
have that every connected nonbipartite planar graph $G$ has a spanning tree $T$
such that $BBC_2(G,T)=4$. This settles a question by Wang, Bu, Montassier and
Raspaud (2012), and generalizes a number of previous partial results to their
question.
