Skip to Main content Skip to Navigation

Complexity of greedy edge-colouring

Frédéric Havet 1 Ana Karolinna Maia de Oliviera 1 Min-Li yu 2 
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - 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.
Complete list of metadata

Cited literature [6 references]  Display  Hide  Download
Contributor : Ana Karolinna Maia De Oliveira Connect in order to contact the contributor
Submitted on : Friday, December 7, 2012 - 11:48:03 AM
Last modification on : Saturday, June 25, 2022 - 11:09:02 PM
Long-term archiving on: : Saturday, December 17, 2016 - 10:30:18 PM


Files produced by the author(s)


  • HAL Id : hal-00762534, version 1



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⟩



Record views


Files downloads