On \(\lambda\)-backbone coloring of cliques with tree backbones in linear time (Q6595513)

A \(\lambda\)-backbone coloring of a graph \(G\) with \(k\) colors and backbone \(H\) (a spanning subgraph of \(G\)) is defined as a proper coloring \(\varsigma:V(G)\rightarrow \{1,2,\dots,k\}\) such that \(|\varsigma(u)-\varsigma(v)|\geq\lambda\) for every \(uv\in E(H)\).\N\NThe \(\lambda\)-backbone coloring number \(\operatorname{BBC}_{\lambda}(G,H)\) of a graph \(G\) with backbone \(H\) is the smallest number \(k\) of colors such that there exists a \(\lambda\)-backbone coloring of \(G\) with \(k\) colors and backbone \(H\).\N\NThe authors show that \(\operatorname{BBC}_{\lambda}(K_{n},F)=\max\{n,2\lambda\}+\Delta^{2}(F)\left\lceil \log(n)\right\rceil \) where \(F\) is a forest, a bound depending on the maximum degree of \(F\).\N\NThey also show a linear algorithm for finding a \(\lambda\)-backbone coloring of \(K_n\) and a backbone \(H\) such that the largest color does not exceed \(\max\{n,2\lambda\}+\Delta^{2}(H)\left\lceil \log(n) \right\rceil\).\N\NFinally, the paper presents an infinite family of trees \(T\) with \(\Delta(T)=3\) (related to the Fibonacci numbers) for which the \(\lambda\)-backbone coloring of \(K_n\) with backbones \(T\) requires at least \(\max\{n,2\lambda\}+\Omega( \log(n) )\) for \(\lambda\) close to \(n/2\).