Can I read Periodic Colorings and Orientations in Infinite Graphs on EtoBox?

Periodic Colorings and Orientations in Infinite Graphs by Abrishami, Tara; Esperet, Louis; Giocanti, Ugo; Hamann, Matthias; Knappe, Paul; Möller, Rögnvaldur G. is a scholarly article available to read on EtoBox.

What is Periodic Colorings and Orientations in Infinite Graphs about?

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 $\chi(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.

Author

Abrishami, Tara; Esperet, Louis; Giocanti, Ugo; Hamann, Matthias; Knappe, Paul; Möller, Rögnvaldur G.

Published

2024

Language

EN