A note on connected greedy edge colouring

Journal Article (2021)
Author(s)

Marthe Bonamy (CEA)

C.E. Groenland (University of Oxford)

Carole Muller (Vrije Universiteit Brussel)

Jonathan Narboni (CEA)

Jakub Pekárek (Charles University)

Alexandra Wesolek (Simon Fraser University)

Affiliation
External organisation
DOI related publication
https://doi.org/10.1016/j.dam.2021.07.018
More Info
expand_more
Publication Year
2021
Language
English
Affiliation
External organisation
Volume number
304
Pages (from-to)
129-136

Abstract

Following a given ordering of the edges of a graph G, the greedy edge colouring procedure assigns to each edge the smallest available colour. The minimum number of colours thus involved is the chromatic index χ(G), and the maximum is the so-called Grundy chromatic index. Here, we are interested in the restricted case where the ordering of the edges builds the graph in a connected fashion. Let χc(G) be the minimum number of colours involved following such an ordering. We show that it is NP-hard to determine whether χc(G)>χ(G). We prove that χ(G)=χc(G) if G is bipartite, and that χc(G)≤4 if G is subcubic.

No files available

Metadata only record. There are no files for this record.