PulseExploreJournal ClubDebatesTrendingResearchersJournals
Instagram
HomeExploreJournal ClubTrending
Synapse
⌘+K
Synapse
March 26, 2026Ars Mathematica Contemporanea0 citationsOpen Access

List distinguishing index of graphs

JKJakub KwaśnyMSMarcin Stawiski

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.

Ask AI
Helpful
Bookmark
Share
View Full Paper

Cite This Study

Kwaśny et al. (2026) studied this question.

synapsesocial.com/papers/69c4cddcfdc3bde44891aa77https://doi.org/10.26493/1855-3974.3536.fc8
Ask AI
Helpful
Bookmark
Share
View Full Paper