This research shows optimal distinguishing colouring in graphs when edge lists satisfy degree conditions, indicating broad applicability.
We say that an edge colouring breaks an automorphism if some edge is mapped to an edge of a different colour. We say that the colouring is distinguishing if it breaks every non-identity automorphism. We show that such a colouring can be chosen from any set of lists associated to the edges of a graph G, whenever the size of each list is at least Δ − 1, where Δ is the maximum degree of G, apart from a few exceptions. This holds both for finite and infinite graphs. The bound is optimal for every Δ ≥ 3, and it is the same as in the non-list version.
No takes yet. Share an insight, caveat, or question.
Kwaśny et al. (2026) studied this question.