Breaking small automorphisms of graphs of arbitrary cardinality
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866918342648922112 |
|---|---|
| author | Stawiski, Marcin |
| author_facet | Stawiski, Marcin |
| contents | We say that an edge colouring $c$ of a graph preserves an automorphism $φ$ if $φ$ maps each edge to an edge of the same colour. Otherwise, we say that $c$ breaks $φ$. We call an automorphism of a graph small if it moves some vertex to its neighbour. We study the edge colourings of graphs that break every small automorphism. Kalinowski, Pilśniak, and Woźniak proved that three colours are enough for such a colouring to exist for every finite graph without isolated edges. They conjectured that two colours are enough for every finite connected graph on at least six vertices. We confirm this conjecture in its more general version, namely for connected finite and infinite graphs of arbitrary cardinality. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_15226 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Breaking small automorphisms of graphs of arbitrary cardinality Stawiski, Marcin Combinatorics 05C15, 05C78 We say that an edge colouring $c$ of a graph preserves an automorphism $φ$ if $φ$ maps each edge to an edge of the same colour. Otherwise, we say that $c$ breaks $φ$. We call an automorphism of a graph small if it moves some vertex to its neighbour. We study the edge colourings of graphs that break every small automorphism. Kalinowski, Pilśniak, and Woźniak proved that three colours are enough for such a colouring to exist for every finite graph without isolated edges. They conjectured that two colours are enough for every finite connected graph on at least six vertices. We confirm this conjecture in its more general version, namely for connected finite and infinite graphs of arbitrary cardinality. |
| title | Breaking small automorphisms of graphs of arbitrary cardinality |
| topic | Combinatorics 05C15, 05C78 |
| url | https://arxiv.org/abs/2602.15226 |