| |
|
|
Abstract: For a graph $G$ and its spanning tree $T$ the {\em backbone chromatic number}, $\BBC (G, T)$, is defined as the minimum $k$ such that there exists a coloring $c\colon V(G) \rightarrow \set{1, 2, \dots, k}$ satisfying $|c(u) - c(v)| \geq 1$ if $uv \in E(G)$ and $|c(u) - c(v)| \geq 2$ if $uv \in E(T)$. Broersma et al.~\cite{broersma07} asked whether there exists a constant $c$ such that for every triangle-free graph $G$ with an arbitrary spanning tree $T$ the inequality $\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 $\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's 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$). Contact the authors: jozef.miskuf@upjs.sk, tancer@kam.mff.cuni.cz Download PDF version of the preprint. |