A note on connected greedy edge colouring

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

doi:10.1016/j.dam.2021.07.018

A note on connected greedy edge colouring

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

extern

Research output: Contribution to journal › Article › Academic › peer-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 language	English
Pages (from-to)	129-136
Number of pages	8
Journal	Discrete Applied Mathematics
Volume	304
DOIs	https://doi.org/10.1016/j.dam.2021.07.018
Publication status	Published - 15 Dec 2021
Externally published	Yes

Bibliographical note

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.

Keywords

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

Access to Document

10.1016/j.dam.2021.07.018

Cite this

@article{16b3052d504f4e36948fcc8e1237323b,

title = "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.",

keywords = "Computational complexity, Connected greedy colouring, Connected greedy edge colouring, Edge colouring, Greedy colouring",

author = "Marthe Bonamy and Carla Groenland and Carole Muller and Jonathan Narboni and Jakub Pek{\'a}rek and Alexandra Wesolek",

note = "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: {\textcopyright} 2021 Elsevier B.V.",

year = "2021",

month = dec,

day = "15",

doi = "10.1016/j.dam.2021.07.018",

language = "English",

volume = "304",

pages = "129--136",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier BV",

}

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 -

A note on connected greedy edge colouring

Abstract

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this