HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

(Circular) backbone colouring: tree backbones in planar graphs

Abstract : 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.
Document type :
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download

Contributor : Frederic Havet Connect in order to contact the contributor
Submitted on : Thursday, November 29, 2012 - 7:01:43 PM
Last modification on : Monday, February 7, 2022 - 9:16:01 AM
Long-term archiving on: : Saturday, December 17, 2016 - 6:35:08 PM


Files produced by the author(s)


  • HAL Id : hal-00759044, version 1


Frédéric Havet, Andrew King, Mathieu Liedloff, Ioan Todinca. (Circular) backbone colouring: tree backbones in planar graphs. [Research Report] RR-8152, INRIA. 2012. ⟨hal-00759044⟩



Record views


Files downloads