Colored Pebble Motion on Graphs (Extended Abstract)

Let r, n and n 1 , … , n r be positive integers with n = n 1 + ⋯ + n r . Let X be a connected graph with n vertices. For 1 ⩽ i ⩽ r , let P i be the ith color class of n i distinct pebbles. A configuration of the set of pebbles P = P 1 ∪ ⋯ ∪ P r 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 , n 1 , … , n r ) of the equivalence classes.