Complexity of greedy edge-colouringReport as inadecuate

Complexity of greedy edge-colouring - Download this document for free, or read online. Document in PDF available to download.

1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués 2 UFC - Universidade Federal do Ceará 3 UFV - University of the Fraser Valley

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.

Author: Frédéric Havet - A Karolinna Maia - Min-Li Yu -



Related documents