Before revision:  We present tight bounds on the convergence rate of the Swendsen-Wang algorithm for the complete d-ary tree that extend to the non-uniqueness region . Specifically, we show that a spatial mixing property known as the Variance Mixing condition introduced by Martinelli et al. ( 2004)implies constant spectral gap of the Swendsen-Wang dynamics . This implies that the relaxation time (i. e., the inverse of the spectral gap) is O(1) for all boundary conditions in the uniqueness region or when \beta<\beta_1 where \beta_1 exceeds the uniqueness threshold for the Ising model  and for the q-state Potts model when q is small with respect to d.
After revision:  We present tight bounds on the convergence rate of the Swendsen-Wang algorithm for the complete d-ary tree that extend to the non-uniqueness region . Specifically, we show that a spatial mixing property known as the Variance Mixing condition introduced by Martinelli et al. ( 2004)implies constant spectral gap of the Swendsen-Wang dynamics on the d-ary tree. We also show that these bounds are asymptotically optimal. As a consequence, we establish \Theta(\log{n all boundary conditions in the uniqueness region or when \beta<\beta_1 where \beta_1 exceeds the uniqueness threshold for the Ising model and for the q-state Potts model when q is small with respect to d.