2024/11/04 by Abrishami, Tara, Esperet, Louis, Giocanti, Ugo +3
#Combinatorics (math.CO) #Dynamical Systems (math.DS) #FOS: Mathematics #Group Theory (math.GR)
paper · doi:10.48550/arxiv.2411.01951
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.