Cyclic successor colorings of regular graphs

For each fixed integer $q\ge 2$, every sufficiently high-degree finite regular graph has an assignment of $q$ colors such that every vertex has a neighbour whose color is its successor modulo $q$. This assignment need not be a proper vertex coloring. If the degree is $r$, independent uniform vertex colors make a given vertex fail with probability $(1-1/q{)}^r$. That event depends on its closed neighbourhood, and has at most $r^2$ dependencies, since only centres within distance two matter. The symmetric Lovász local lemma therefore gives such an assignment whenever $e(r^2+1)(1-1/q{)}^r\le 1$, which holds for all sufficiently large $r$.

Choose one successor neighbour from each vertex. The resulting directed graph has outdegree one and hence contains a directed cycle. Its color increases once modulo $q$ on each step, so its length is divisible by $q$. Thus a nontrivial cycle of length a multiple of $q$ is obtained when $q\ge 3$; for $q=2$ a directed two-cycle may simply traverse one undirected edge twice, so this last cycle inference needs a separate argument if an undirected simple cycle is required.