Complexity of greedy edge-colouring

Frédéric Havet 1 A Karolinna Maia 2 Min-Li Yu 3
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 : The Grundy index of a graph G = (V, E) is the greatest number of colours that the greedy edge-colouring algorithm can use on G. We prove that the problem of determining the Grundy index of a graph G = (V, E) is NP-hard for general graphs. We also show that this problem is polynomial-time solvable for caterpillars. More specifically, we prove that the Grundy index of a caterpillar is (G) or (G) + 1 and present a polynomial-time algorithm to determine it exactly.
Type de document :
Article dans une revue
Journal of the Brazilian Computer Society, Springer Verlag, 2015, 21 (18), 〈10.1186/s13173-015-0036-x〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01233312
Contributeur : Frederic Havet <>
Soumis le : vendredi 18 décembre 2015 - 12:34:18
Dernière modification le : samedi 19 décembre 2015 - 01:05:38
Document(s) archivé(s) le : samedi 29 avril 2017 - 00:39:49

Fichier

soumis-bresil.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Frédéric Havet, A Karolinna Maia, Min-Li Yu. Complexity of greedy edge-colouring. Journal of the Brazilian Computer Society, Springer Verlag, 2015, 21 (18), 〈10.1186/s13173-015-0036-x〉. 〈hal-01233312〉

Partager

Métriques

Consultations de
la notice

197

Téléchargements du document

164