The Computational Complexity of $\lambda$-Backbone Colorings of Graphs with $n$-Complete Backbones

Abstract

Given an integer $\lambda \ge 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$.