An exact algorithm for the generalized list T-coloring problem

Abstract : The generalized list T-coloring is a common generalization of many graph coloring models, including classical coloring, L(p,q)-labeling, channel assignment and T-coloring. Every vertex from the input graph has a list of permitted labels. Moreover, every edge has a set of forbidden differences. We ask for a labeling of vertices of the input graph with natural numbers, in which every vertex gets a label from its list of permitted labels and the difference of labels of the endpoints of each edge does not belong to the set of forbidden differences of this edge. In this paper we present an exact algorithm solving this problem, running in time O*((τ+2)n), where τ is the maximum forbidden difference over all edges of the input graph and n is the number of its vertices. Moreover, we show how to improve this bound if the input graph has some special structure, e.g. a bounded maximum degree, no big induced stars or a perfect matching.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 3 (in progress) (3), pp.77--94
Liste complète des métadonnées

Littérature citée [28 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01188909
Contributeur : Coordination Episciences Iam <>
Soumis le : lundi 31 août 2015 - 17:03:38
Dernière modification le : jeudi 7 septembre 2017 - 01:03:49
Document(s) archivé(s) le : mardi 1 décembre 2015 - 10:43:42

Fichier

dmtcs-16-3-5.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01188909, version 1

Collections

Citation

Konstanty Junosza-Szaniawski, Pawel Rzazewski. An exact algorithm for the generalized list T-coloring problem. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 3 (in progress) (3), pp.77--94. 〈hal-01188909〉

Partager

Métriques

Consultations de la notice

39

Téléchargements de fichiers

106