Id: arxiv/2602.15221 Url: https://arxiv.org/abs/2602.15221 Tags: math.CO, math.LO Score: 0 Title: Irreducible distinguishing colourings and the Axiom of Choice Domain: math.CO Source: arxiv Authors: Marcin Stawiski Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-02-16 Page: https://delphi.science/r/arxiv/2602.15221 We say that a vertex or edge colouring of a graph is distinguishing if the only automorphism that preserves this colouring is the identity. A (proper) distinguishing colouring is irreducible if there is no possibility of merging two non-empty classes of colours to obtain a (proper) distinguishing colouring. We show that every graph has an irreducible (proper) distinguishing vertex colouring and that every graph without isolated edge and with at most one isolated vertex has an irreducible (proper) distinguishing edge colouring. Moreover, we show that the existence of any of these colourings…