Skip to Main content Skip to Navigation
New interface
Journal articles

Complexity of greedy edge-colouring

Frédéric Havet 1 Ana Karolinna Maia de Oliviera 2 Min-Li Yu 3 
1 COATI - Combinatorics, Optimization and Algorithms 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 (G) or (G) + 1 and present a polynomial-time algorithm to determine it exactly.
Document type :
Journal articles
Complete list of metadata

Cited literature [6 references]  Display  Hide  Download
Contributor : Frederic Havet Connect in order to contact the contributor
Submitted on : Friday, December 18, 2015 - 12:34:18 PM
Last modification on : Thursday, August 4, 2022 - 4:58:28 PM
Long-term archiving on: : Saturday, April 29, 2017 - 12:39:49 AM


Files produced by the author(s)




Frédéric Havet, Ana Karolinna Maia de Oliviera, Min-Li Yu. Complexity of greedy edge-colouring. Journal of the Brazilian Computer Society, 2015, 21 (18), ⟨10.1186/s13173-015-0036-x⟩. ⟨hal-01233312⟩



Record views


Files downloads