For a graph $G$ and its spanning tree $T$ the backbone chromatic number, $\mathrm{BBC}(G,T)$, is defined as the minimum $k$ such that there exists a coloring $c\colon V(G)\rightarrow\{1,2,\dots,k\}$ satisfying $|c(u)-c(v)|\geq1$ if $uv\in E(G)$ and $|c(u)-c(v)|\geq2$ if $uv\in E(T)$. Broersma et al. [J. Graph Theory, 55 (2007), pp. 137-152] asked whether there exists a constant $c$ such that for every triangle-free graph $G$ with an arbitrary spanning tree $T$ the inequality $\mathrm{BBC}(G,T)\leq\chi(G)+c$ holds. We answer this question negatively by showing the existence of triangle-free graphs $R_n$ and their spanning trees $T_n$ such that $\mathrm{BBC}(R_n,T_n)=2\chi(R_n)-1=2n-1$. In order to answer the question, we obtain a result of independent interest. We modify the well-known Mycielski construction and construct triangle-free graphs $J_n$ for every integer $n$, with chromatic number $n$ and 2-tuple chromatic number $2n$ (here 2 can be replaced by any integer $t$).
['Jozef Miškuf', 'Riste Škrekovski', 'Martin Tancer']
Backbone Colorings and Generalized Mycielski Graphs