Irreducible distinguishing colourings and the Axiom of Choice
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908837363056640 |
|---|---|
| author | Stawiski, Marcin |
| author_facet | Stawiski, Marcin |
| contents | 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 for every connected graph (not isomorphic to $K_2$) is equivalent to the Axiom of Choice. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_15221 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Irreducible distinguishing colourings and the Axiom of Choice Stawiski, Marcin Combinatorics Logic 05C15, 03E25, 05C25, 05C63 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 for every connected graph (not isomorphic to $K_2$) is equivalent to the Axiom of Choice. |
| title | Irreducible distinguishing colourings and the Axiom of Choice |
| topic | Combinatorics Logic 05C15, 03E25, 05C25, 05C63 |
| url | https://arxiv.org/abs/2602.15221 |