Complexity of greedy edge-colouring

Brazilian Computer Society. Journal

ric Havet¹  Min-Li Yu²  dé³  Fré⁵  A. Karolinna Maia⁶ 

[1] ã, Fortaleza, Brazil;Departamento de ComputaçDepartment of Maths and Statistics University of the Fraser Valley, Abbotsford, BC, Canada;Projet Coati I3S (CNRS, UNSA) and INRIA, Sophia Antipolis, Valbonne, France;o, ParGO, Universidade Federal do Ceará

关键词: Greedy Algorithm;    Maximum Degree;    Chromatic Number;    Line Graph;    Channel Assignment;   

DOI  :  10.1186/s13173-015-0036-x

学科分类：农业科学（综合）

来源: Springer U K

【 摘 要 】

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.

【 授权许可】

CC BY