8714 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
• oai:hal.inria.fr:hal-00762534
• From:
• Submitted on: Friday, 7 December 2012 11:48:03
• Updated on: Wednesday, 23 January 2013 14:27:34