  We present improved bounds for randomly sampling $k$-colorings of graphs with
maximum degree $\Delta$; our results hold without any further assumptions on
the graph. The Glauber dynamics is a simple single-site update Markov chain.
Jerrum (1995) proved an optimal $O(n\log{n})$ mixing time bound for Glauber
dynamics whenever $k>2\Delta$ where $\Delta$ is the maximum degree of the input
graph. This bound was improved by Vigoda (1999) to $k > (11/6)\Delta$ using a
"flip" dynamics which recolors (small) maximal 2-colored components in each
step. Vigoda's result was the best known for general graphs for 20 years until
Chen et al. (2019) established optimal mixing of the flip dynamics for $k >
(11/6 - \epsilon ) \Delta$ where $\epsilon \approx 10^{-5}$. We present the
first substantial improvement over these results. We prove an optimal mixing
time bound of $O(n\log{n})$ for the flip dynamics when $k \geq 1.809 \Delta$.
This yields, through recent spectral independence results, an optimal
$O(n\log{n})$ mixing time for the Glauber dynamics for the same range of
$k/\Delta$ when $\Delta=O(1)$. Our proof utilizes path coupling with a simple
weighted Hamming distance for "unblocked" neighbors.
