Backbone coloring for graphs with degree 4

Abstract

The $\lambda$-backbone coloring of the graph $G$ with backbone $H$ is a graph-coloring problem in which we are given a graph $G$ and a subgraph $H$, and we want to assign colors to vertices in such a way that the endpoints of every edge from $G$ have different colors, and the endpoints of every edge from $H$ are assigned colors which differ by at least $\lambda$. In this paper we pursue research on backbone coloring of bounded-degree graphs with well-known classes of backbones. Our result is an almost complete classification of the complexity of deciding whether $BB{C}_{\lambda }(G,H)\le k$ for graphs with maximum degree at most $4$ and matching, galaxy, Hamiltonian path, and spanning tree backbones. We also determine the effect of allowing isolated vertices in matching and galaxy backbones.