  A coupling of random walkers on the same finite graph, who take turns
sequentially, is said to be an avoidance coupling if the walkers never collide.
Previous studies of these processes have focused almost exclusively on complete
graphs, in particular how many walkers an avoidance coupling can include. For
other graphs, apart from special cases, it has been unsettled whether even two
non-colliding simple random walkers can be coupled. In this article, we
construct such a coupling on (i) any $d$-regular graph avoiding a fixed
subgraph depending on $d$; and (ii) any square-free graph with minimum degree
at least three. A corollary of the first result is that a uniformly random
regular graph on $n$ vertices admits an avoidance coupling with high
probability.
