List circular backbone colouring

Frédéric Havet 1 Andrew King 2
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : A natural generalization of graph colouring involves taking colours from a metric space and insisting that the endpoints of an edge receive colours separated by a minimum distance dictated by properties of the edge. In the q-backbone colouring problem, these minimum distances are either q or 1, depending on whether or not the edge is in the backbone. In this paper we consider the list version of this problem, with particular focus on colours in ℤp - this problem is closely related to the problem of circular choosability. We first prove that the list circular q-backbone chromatic number of a graph is bounded by a function of the list chromatic number. We then consider the more general problem in which each edge is assigned an individual distance between its endpoints, and provide bounds using the Combinatorial Nullstellensatz. Through this result and through structural approaches, we achieve good bounds when both the graph and the backbone belong to restricted families of graphs.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, 16 (1), pp.89--104
Liste complète des métadonnées

https://hal.inria.fr/hal-01179209
Contributeur : Hélène Lowinger <>
Soumis le : mercredi 22 juillet 2015 - 09:14:44
Dernière modification le : mercredi 14 décembre 2016 - 01:07:21
Document(s) archivé(s) le : vendredi 23 octobre 2015 - 10:23:27

Fichier

dmtcs-16-1-6.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01179209, version 1

Collections

Citation

Frédéric Havet, Andrew King. List circular backbone colouring. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, 16 (1), pp.89--104. <hal-01179209>

Partager

Métriques

Consultations de
la notice

193

Téléchargements du document

110