Complexity of greedy edge-colouring - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2012

Complexity of greedy edge-colouring

Résumé

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.
Fichier principal
Vignette du fichier
RR-8171.pdf (727.29 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00762534 , version 1 (07-12-2012)

Identifiants

  • HAL Id : hal-00762534 , version 1

Citer

Frédéric Havet, Ana Karolinna Maia de Oliviera, Min-Li Yu. Complexity of greedy edge-colouring. [Research Report] RR-8171, INRIA. 2012, pp.13. ⟨hal-00762534⟩
162 Consultations
569 Téléchargements

Partager

Gmail Facebook X LinkedIn More