(Circular) backbone colouring: tree backbones in planar graphs

Consider an undirected graph G and a subgraph H of G, on the same vertex set. The q-backbone chromatic number BBCq(G,H) is the minimum k such that G can be properly coloured with colours from {1, ..., k}, and moreover for each edge of H, the colours of its ends differ by at least q. In this paper we focus on the case when G is planar and H 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.On considère un graphe G (non-orienté) et un sous-graphe H de G. Le nombre chromatique q-dorsal BBCq(G,H) est le plus petit entier k tel que G puisse être coloré proprement avec les couleurs {1, ...,k} de telle sorte qu'en plus pour toute arête de H, les couleurs de ses deux extrémités diff'erent d'au moins q. Dans ce rapport, nous étudions le cas où G est planaire et H est une forêt. Nous donnons une série de résultats de NP-complétude ainsi que des bornes supérieures pour BBCq(G,H), suivant le type de forêt (couplage, galaxie, arbre couvrant). Nous abordons également une version circulaire du problème