Szczegóły publikacji
Opis bibliograficzny
On asymmetric colourings of graphs with bounded degrees and infinite motion / Florian Lehner, Monika PILŚNIAK, Marcin STAWISKI // Ars Mathematica Contemporanea ; ISSN 1855-3966 . — 2025 — vol. 25 no. 4 art. no. P409, s. 1-9. — Bibliogr. s. 8-9, Abstr. — Publikacja dostępna online od: 2025-10-17
Autorzy (3)
- Lehner Florian
- AGHPilśniak Monika
- AGHStawiski Marcin
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 164091 |
|---|---|
| Data dodania do BaDAP | 2025-11-19 |
| Tekst źródłowy | URL |
| DOI | 10.26493/1855-3974.2878.a61 |
| Rok publikacji | 2025 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Creative Commons | |
| Czasopismo/seria | Ars Mathematica Contemporanea |
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(Δ).
