(Circular) backbone colouring: tree backbones in planar graphs

Frederic Havet; Andrew D. King; Mathieu Liedloff; Ioan Todinca

hal-00759044, version 1

(Circular) backbone colouring: tree backbones in planar graphs

Frederic Havet () ¹, Andrew D. King ^2, 3, Mathieu Liedloff () ⁴, Ioan Todinca () ⁴

N° RR-8152 (2012)

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.

1: MASCOTTE (INRIA Sophia Antipolis / Laboratoire I3S)
INRIA – Université Nice Sophia Antipolis [UNS] – CNRS : UMR7271
2: Department of Mathematics
Simon Fraser University
3: Department of computer science [Burnaby]
Simon Fraser University
4: Laboratoire d'Informatique Fondamentale d'Orléans (LIFO)
Université d'Orléans : EA4022 – Ecole Nationale Supérieure d'Ingénieurs de Bourges

hal-00759044, version 1
http://hal.inria.fr/hal-00759044
oai:hal.inria.fr:hal-00759044
From: Frederic Havet <>
Submitted on: Thursday, 29 November 2012 19:01:43
Updated on: Friday, 30 November 2012 11:23:55

See detailed view

Associated documents

PDF :

Export

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="report"><head>Research reports</head>
<biblStruct type="report" xml:id="hal-00759044"><monogr>
<author><persName><forename>Frederic</forename><surname>Havet</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Sophia Antipolis / Laboratoire I3S</orgName>
<orgName type="team">MASCOTTE</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université Nice Sophia Antipolis [UNS]</orgName>
<orgName type="institution">CNRS : UMR7271</orgName>
</affiliation>
</author>
<author><persName><forename>Andrew</forename><surname>King</surname></persName>
<affiliation>
<orgName type="team">Department of Mathematics</orgName>
<country>CA</country>
<orgName type="institution">Simon Fraser University</orgName>
</affiliation>
<affiliation>
<orgName type="team">Department of computer science [Burnaby]</orgName>
<country>CA</country>
<orgName type="institution">Simon Fraser University</orgName>
</affiliation>
</author>
<author><persName><forename>Mathieu</forename><surname>Liedloff</surname></persName>
<affiliation>
<orgName type="laboratory">LIFO</orgName>
<orgName type="team">Laboratoire d'Informatique Fondamentale d'Orléans</orgName>
<country>FR</country>
<orgName type="institution">Université d'Orléans : EA4022</orgName>
<orgName type="institution">Ecole Nationale Supérieure d'Ingénieurs de Bourges</orgName>
</affiliation>
</author>
<author><persName><forename>Ioan</forename><surname>Todinca</surname></persName>
<affiliation>
<orgName type="laboratory">LIFO</orgName>
<orgName type="team">Laboratoire d'Informatique Fondamentale d'Orléans</orgName>
<country>FR</country>
<orgName type="institution">Université d'Orléans : EA4022</orgName>
<orgName type="institution">Ecole Nationale Supérieure d'Ingénieurs de Bourges</orgName>
</affiliation>
</author>
<title type="main" level="m">(Circular) backbone colouring: tree backbones in planar graphs</title><title type="main" level="m">(Circular) backbone colouring: tree backbones in planar graphs</title><imprint><biblScope type="publicationDate">2012-11-00</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/hal-00759044</idno><idno type="HALFile">http://hal.inria.fr/hal-00759044/PDF/RR-8152.pdf</idno></biblStruct>
</listBibl>
</listBibl>