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
Reports

(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 :
Reports
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/hal-00759044
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

File

RR-8152.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00759044, version 1

Citation

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⟩

Share

Metrics

Record views

402

Files downloads

137