Menu
Given an integer \( \lambda \geq 2 \), a graph \( G = (V, E) \) and a spanning subgraph \( H \) of \( G \) (the backbone of \( G \)), a \( \lambda \)-backbone coloring of \( (G, H) \) is a proper vertex coloring \( V \to \{1, 2, \dots\} \) of \( G \), in which the colors assigned to adjacent vertices in \( H \) differ by at least \( \lambda \). We study the computational complexity of the problem “Given a graph \( G \) with a backbone \( H \), and an integer \( \ell \), is there a \( \lambda \)-backbone coloring of \( (G, H) \) with at most \( \ell \) colors?” Of course, this general problem is NP-complete. In this paper, we consider this problem for collections of pairwise disjoint complete graphs with order \( n \). We show that the complexity jumps from polynomially solvable to NP-complete between \( \ell = (n – 1)\lambda \) and \( \ell = (n – 1)\lambda + 1 \).