Backbone Colorings and Generalized Mycielski Graphs
Jozef Miškuf, Riste Škrekovski, Martin Tancer · SIAM Journal on Discrete Mathematics · 2009
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).