A note on connected greedy edge colouring

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.