8481 articles  [english version]

hal-00762534, version 1

Complexity of greedy edge-colouring

Frédéric Havet () 1, Ana Karolinna Maia () 1, Min-Li Yu () 2

N° RR-8171 (2012)

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.

  • 1 :  MASCOTTE (INRIA Sophia Antipolis / Laboratoire I3S)
  • INRIA – Université Nice Sophia Antipolis [UNS] – CNRS : UMR7271
  • 2 :  Department of Mathematics and Statistics [Fraser Valley]
  • University College of the Fraser Valley
  • Domaine : Informatique/Algorithme et structure de données
  • Mots-clés : Edge colouring – greedy colouring – greedy algorithm – line graphs – caterpillars – NP-complete.
  • Référence interne : RR-8171
 
  • hal-00762534, version 1
  • http://hal.inria.fr/hal-00762534
  • oai: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 : Mercredi 23 Janvier 2013, 14:27:34