A note on connected greedy edge colouring
2021
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:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
6
References
1
Citations
NaN
KQI