A note on connected greedy edge colouring

Marthe Bonamy, Carla Groenland, Carole Muller, Jonathan Narboni, Jakub Pekárek, Alexandra Wesolek

Research output: Contribution to journalArticleAcademicpeer-review

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.

Original languageEnglish
Pages (from-to)129-136
Number of pages8
JournalDiscrete Applied Mathematics
Volume304
DOIs
Publication statusPublished - 15 Dec 2021

Keywords

  • Computational complexity
  • Connected greedy colouring
  • Connected greedy edge colouring
  • Edge colouring
  • Greedy colouring

Fingerprint

Dive into the research topics of 'A note on connected greedy edge colouring'. Together they form a unique fingerprint.

Cite this