On {\lambda}-backbone coloring of cliques with tree backbones in linear time

A $\lambda$-backbone coloring of a graph $G$ with its subgraph (also called a backbone) $H$ is a function $c\text{\hspace{0.17em}⁣}:V(G)\to \{1,\dots ,k\}$ ensuring that $c$ is a proper coloring of $G$ and for each $\{u,v\}\in E(H)$ it holds that $\mathrm{\mid }c(u)-c(v)\mathrm{\mid }\ge \lambda$. In this paper we propose a way to color cliques with tree and forest backbones in linear time that the largest color does not exceed $\max \{n,2\lambda \}+\mathrm{\Delta }(H{)}^2\lceil \log n\rceil$. This result improves on the previously existing approximation algorithms as it is $(\mathrm{\Delta }(H{)}^2\lceil \log n\rceil )$-absolutely approximate, i.e. with an additive error over the optimum. We also present an infinite family of trees $T$ with $\mathrm{\Delta }(T)=3$ for which the coloring of cliques with backbones $T$ require to use at least $\max \{n,2\lambda \}+\mathrm{\Omega }(\log n)$ colors for $\lambda$ close to $\frac{n}{2}$.