  We start by introducing avoidance coupling of Markov chains, with an overview
of existing results. We then introduce and motivate a new notion, uniform
avoidance coupling. We show that the only Markovian avoidance coupling on a
cycle is of this type, and that uniform avoidance coupling of simple random
walks is impossible on trees, and prove that it is possible on several classes
of graphs. We also derive a condition on the vertex neighborhoods in a graph
equivalent to that graph admitting a uniform avoidance coupling of simple
random walks, and an algorithm that tests this with run time polynomial in the
number of vertices.
