| Naslov: | On asymmetric colourings of graphs with bounded degrees and infinite motion |
|---|
| Avtorji: | ID Lehner, Florian (Avtor)
ID Pilśniak, Monika (Avtor)
ID Stawiski, Marcin (Avtor) |
|---|
| Datoteke: |  RAZ_Lehner,Pilśniak,Stawiski_2025.pdf (299,41 KB)
MD5: EF917F66F0DB76D41F80E6EEF9B38115
|
|---|
| Jezik: | Angleški jezik |
|---|
| Vrsta gradiva: | Članek v reviji |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: | ZUP - Založba Univerze na Primorskem
|
|---|
| Opis: | 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(Δ). |
|---|
| Ključne besede: | infinite graph, asymmetric colouring, infinite motion |
|---|
| Status publikacije: | Objavljeno |
|---|
| Verzija publikacije: | Objavljena publikacija |
|---|
| Datum objave: | 17.10.2025 |
|---|
| Založnik: | Založba Univerze na Primorskem |
|---|
| Leto izida: | 2025 |
|---|
| Št. strani: | 9 str. |
|---|
| Številčenje: | Vol. 25, no. 4, [article no.] P4.09 |
|---|
| PID: | 20.500.12556/RUP-22022  |
|---|
| UDK: | 519.17 |
|---|
| eISSN: | 1855-3974 |
|---|
| DOI: | https://doi.org/10.26493/1855-3974.2878.a61 |
|---|
| Datum objave v RUP: | 22.10.2025 |
|---|
| Število ogledov: | 288 |
|---|
| Število prenosov: | 3 |
|---|
| Metapodatki: |    |
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Skupna ocena: | (0 glasov) |
|---|
| Vaša ocena: | Ocenjevanje je dovoljeno samo prijavljenim uporabnikom. |
|---|
| Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
