Backbone coloring for graphs with degree 4

Abstract

The $\hat{I}»$-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 $\hat{I}»$. 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 problems in the form $BB{C}_{\hat{I}}»(G,H)\le \hat{I}»+k$ for graphs with maximum degree $4$ and backbones from the following classes: paths, trees, matchings, and galaxies.