| Title: | On asymmetric colourings of graphs with bounded degrees and infinite motion |
|---|
| Authors: | ID Lehner, Florian (Author)
ID Pilśniak, Monika (Author)
ID Stawiski, Marcin (Author) |
|---|
| Files: |  RAZ_Lehner,Pilśniak,Stawiski_2025.pdf (299,41 KB)
MD5: EF917F66F0DB76D41F80E6EEF9B38115
|
|---|
| Language: | English |
|---|
| Work type: | Article |
|---|
| Typology: | 1.01 - Original Scientific Article |
|---|
| Organization: | ZUP - University of Primorska Press
|
|---|
| Abstract: | A vertex colouring of a graph is called asymmetric if the only automorphism which preserves it is the identity. Tucker conjectured that if every automorphism of a connected, locally finite graph moves infinitely many vertices, then there is an asymmetric colouring with 2 colours. This conjecture was recently confirmed by Babai, using the heavy machinery of the classification of finite simple groups. We make progress towards a purely combinatorial proof of this conjecture in the special case of graphs with bounded maximal degree. More precisely, using only elementary combinatorial methods, we prove that if every automorphism of a connected graph with maximal degree Δ moves infinitely many vertices, then there is an asymmetric colouring using O(\sqrt(Δ) log(Δ)) colours. This is the first improvement which does not depend on the classification of finite simple groups over the trivial bound of O(Δ). |
|---|
| Keywords: | infinite graph, asymmetric colouring, infinite motion |
|---|
| Publication status: | Published |
|---|
| Publication version: | Version of Record |
|---|
| Publication date: | 17.10.2025 |
|---|
| Publisher: | Založba Univerze na Primorskem |
|---|
| Year of publishing: | 2025 |
|---|
| Number of pages: | 9 str. |
|---|
| Numbering: | Vol. 25, no. 4, [article no.] P4.09 |
|---|
| PID: | 20.500.12556/RUP-22022  |
|---|
| UDC: | 519.17 |
|---|
| eISSN: | 1855-3974 |
|---|
| DOI: | https://doi.org/10.26493/1855-3974.2878.a61 |
|---|
| Publication date in RUP: | 22.10.2025 |
|---|
| Views: | 313 |
|---|
| Downloads: | 3 |
|---|
| Metadata: |    |
|---|
|
:
|
Copy citation |
|---|
| | | | Average score: | (0 votes) |
|---|
| Your score: | Voting is allowed only for logged in users. |
|---|
| Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
