Complexity of greedy edge-colouring

Frédéric Havet 1 Ana Karolinna Maia 1 Min-Li Yu 2
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization 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 $\Delta(G)$ or $\Delta(G)+1$ and present a polynomial-time algorithm to determine it exactly.
Type de document :
Rapport
[Research Report] RR-8171, INRIA. 2012, pp.13
Liste complète des métadonnées

https://hal.inria.fr/hal-00762534
Contributeur : Ana Karolinna Maia de Oliveira <>
Soumis le : vendredi 7 décembre 2012 - 11:48:03
Dernière modification le : samedi 17 septembre 2016 - 01:35:29
Document(s) archivé(s) le : samedi 17 décembre 2016 - 22:30:18

Fichier

RR-8171.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00762534, version 1

Collections

Citation

Frédéric Havet, Ana Karolinna Maia, Min-Li Yu. Complexity of greedy edge-colouring. [Research Report] RR-8171, INRIA. 2012, pp.13. <hal-00762534>

Partager

Métriques

Consultations de
la notice

242

Téléchargements du document

433