Periodic colorings and orientations in infinite graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912891924381696 |
|---|---|
| author | Abrishami, Tara Esperet, Louis Giocanti, Ugo Hamann, Matthias Knappe, Paul Möller, Rögnvaldur G. |
| author_facet | Abrishami, Tara Esperet, Louis Giocanti, Ugo Hamann, Matthias Knappe, Paul Möller, Rögnvaldur G. |
| contents | We study the existence of periodic colorings and orientations in locally finite graphs. A coloring or orientation of a graph $G$ is periodic if the resulting colored or oriented graph is quasi-transitive, meaning that $V(G)$ has finitely many orbits under the action of the group of automorphisms of $G$ preserving the coloring or the orientation. When such a periodic coloring or orientation of $G$ exists, $G$ itself must be quasi-transitive and it is natural to investigate when quasi-transitive graphs have such periodic colorings or orientations. We provide examples of Cayley graphs with no periodic orientation or non-trivial coloring, and examples of quasi-transitive graphs of treewidth 2 without periodic orientation or proper coloring. On the other hand we show that every quasi-transitive graph $G$ of bounded pathwidth has a periodic proper coloring with $χ(G)$ colors and a periodic orientation. We relate these problems with techniques and questions from symbolic dynamics and distributed computing and conclude with a number of open problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_01951 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Periodic colorings and orientations in infinite graphs Abrishami, Tara Esperet, Louis Giocanti, Ugo Hamann, Matthias Knappe, Paul Möller, Rögnvaldur G. Combinatorics Dynamical Systems Group Theory We study the existence of periodic colorings and orientations in locally finite graphs. A coloring or orientation of a graph $G$ is periodic if the resulting colored or oriented graph is quasi-transitive, meaning that $V(G)$ has finitely many orbits under the action of the group of automorphisms of $G$ preserving the coloring or the orientation. When such a periodic coloring or orientation of $G$ exists, $G$ itself must be quasi-transitive and it is natural to investigate when quasi-transitive graphs have such periodic colorings or orientations. We provide examples of Cayley graphs with no periodic orientation or non-trivial coloring, and examples of quasi-transitive graphs of treewidth 2 without periodic orientation or proper coloring. On the other hand we show that every quasi-transitive graph $G$ of bounded pathwidth has a periodic proper coloring with $χ(G)$ colors and a periodic orientation. We relate these problems with techniques and questions from symbolic dynamics and distributed computing and conclude with a number of open problems. |
| title | Periodic colorings and orientations in infinite graphs |
| topic | Combinatorics Dynamical Systems Group Theory |
| url | https://arxiv.org/abs/2411.01951 |