On λ-backbone coloring of cliques with tree backbones in linear time

Abstract

A $\lambda$-backbone coloring of a graph $G$ with its subgraph (also called a backbone) $H$ is a function $c: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 $|c(u)-c(v)|\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 \}+\Delta (H{)}^2\lceil \log n\rceil$. This result improves on the previously existing approximation algorithms as it is $(\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 $\Delta (T)=3$ for which the coloring of cliques with backbones $T$ require to use at least $\max \{n,2\lambda \}+\Omega (\log n)$ colors for $\lambda$ close to $\frac{n}{2}$.

arXiv comment21 pages, 3 figures