TY - JOUR

T1 - A note on connected greedy edge colouring

AU - Bonamy, Marthe

AU - Groenland, Carla

AU - Muller, Carole

AU - Narboni, Jonathan

AU - Pekárek, Jakub

AU - Wesolek, Alexandra

N1 - Funding Information:
M. Bonamy is supported by ANR, France Project GrR (ANR-18-CE40-0032).C. Muller is supported by the Luxembourg National Research Fund (FNR) Grant No. 11628910 and was supported by the FNRS, Belgium during her research stay in Bordeaux.J. Pek?rek is supported by GAUK, Czechia grant 118119 (Algorithms for graphs with restrictions on cycles).A. Wesolek is supported by the Vanier Canada Graduate Scholarships program.We are grateful to LaBRI for providing us with a great working environment during the time at which the research was conducted. The second and sixth author are thankful for the funding of the ANR, France Project GrR (ANR-18-CE40-0032) that made their visit possible.
Publisher Copyright:
© 2021 Elsevier B.V.

PY - 2021/12/15

Y1 - 2021/12/15

N2 - 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.

AB - 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.

KW - Computational complexity

KW - Connected greedy colouring

KW - Connected greedy edge colouring

KW - Edge colouring

KW - Greedy colouring

UR - http://www.scopus.com/inward/record.url?scp=85111518530&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2021.07.018

DO - 10.1016/j.dam.2021.07.018

M3 - Article

SN - 0166-218X

VL - 304

SP - 129

EP - 136

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -