On the Existence of Tree Backbones that Realize the Chromatic Number on a Backbone Coloring

A proper $k$-coloring of a graph $G=(V,E)$ is a function $c: V(G)\to {1,\ldots,k}$suchthat$c(u)\neq c(v)$,forevery$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 $\mid c(u)-c(v)\mid \ge q$, for every edge $uv\in E(H)$. The $q$-backbone chromatic number $BB{C}_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 $BB{C}_2(G,T)=\chi (G)$, if $\chi (G)\ge 4$, or $BB{C}_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 $BB{C}_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.