  We show that the $4$-state anti-ferromagnetic Potts model with interaction
parameter $w\in(0,1)$ on the infinite $(d+1)$-regular tree has a unique Gibbs
measure if $w\geq 1-\frac{4}{d+1}$ for all $d\geq 4$. This is tight since it is
known that there are multiple Gibbs measures when $0\leq w<1-\frac{4}{d+1}$ and
$d\geq 4$.
  We moreover give a new proof of the uniqueness of the Gibbs measure for the
$3$-state Potts model on the $(d+1)$-regular tree for $w\geq 1-\frac{3}{d+1}$
when $d\geq 3$ and for $w\in (0,1)$ when $d=2$.
