What question did this study set out to answer?

The aim is to determine conditions for edge colourings that distinguish non-identity automorphisms in graphs.

March 26, 2026Ars Mathematica Contemporanea0 citationsOpen Access

List distinguishing index of graphs

JKJakub KwaśnyJagiellonian University MSMarcin StawiskiJagiellonian University

Key Points

The aim is to determine conditions for edge colourings that distinguish non-identity automorphisms in graphs.
Examined edge colourings that break automorphisms in graphs.
Defined conditions for colourings based on edge lists.
Considered both finite and infinite graphs with a focus on maximum degree.
Found that a distinguishing colouring can be selected from edge lists of size at least Δ − 1.
Confirmed the optimality of this approach for all graphs with Δ ≥ 3.
Identified exceptions where the conditions may not hold.

Abstract

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.

AIに質問

Bookmark

View Full Paper