(Circular) backbone colouring: Forest backbones in planar graphs.

Abstract: Consider an undirected graph and a subgraph of , on the same vertex set. The -backbone chromatic number is the minimum such that can be properly coloured with colours from , and moreover for each edge of , the colours of its ends differ by at least . In this paper we focus on the case when is planar and is a forest. We give a series of NP-hardness results as well as upper bounds for , depending on the type of the forest (matching, galaxy, spanning tree). Eventually, we discuss a circular version of the problem. [Copyright &y& Elsevier]