8485 articles  [version française]

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)

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.

  • 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
  • Domain : Computer Science/Data Structures and Algorithms
  • Keywords : Edge colouring – greedy colouring – greedy algorithm – line graphs – caterpillars – NP-complete.
  • Internal note : RR-8171
 
  • hal-00762534, version 1
  • http://hal.inria.fr/hal-00762534
  • oai:hal.inria.fr:hal-00762534
  • From: Ana Karolinna Maia De Oliveira <>
  • Submitted on: Friday, 7 December 2012 11:48:03
  • Updated on: Wednesday, 23 January 2013 14:27:34