Combinatorial 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 \(\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.

Mathematics Subject Classifications: 05C15, 05C25, 20F65

Keywords: Quasi-transitive graphs, periodic colorings, simple groups