Colored Pebble Motion on Graphs (Extended Abstract)

Let r, n and n1,…,nr be positive integers with n=n1+⋯+nr. Let X be a connected graph with n vertices. For 1⩽i⩽r, let Pi be the ith color class of ni distinct pebbles. A configuration of the set of pebbles P=P1∪⋯∪Pr on X is defined as a bijection from the set of vertices of X to P. A move of pebbles is defined as exchanging two pebbles with mutually distinct colors on the two endvertices of a common edge. For a pair of configurations f and g, we write f∼g if f can be transformed into g by a sequence of finite moves. The relation ∼ is an equivalence relation on the set of all the configurations of P on X. We study the number c(X,n1,…,nr) of the equivalence classes.