(Circular) backbone colouring: Forest backbones in planar graphs

Consider an undirected graph GG and a subgraph HH of GG, on the same vertex set. The qq-backbone chromatic number  BBCq(G,H) is the minimum kk such that GG can be properly coloured with colours from {1,…,k}{1,…,k}, and moreover for each edge of HH, the colours of its ends differ by at least qq. In this paper we focus on the case when GG is planar and HH is a forest. We give a series of NP-hardness results as well as upper bounds for BBCq(G,H), depending on the type of the forest (matching, galaxy, spanning tree). Eventually, we discuss a circular version of the problem.