Bonamy–Bousquet–Feghali–Johnson quadratic diameter conjecture for coloring graphs

Let $G=(V,E)$ be a $d$-degenerate graph, and let $k>d$ be an integer. The graph $\mathcal{K}_k(G)$ has as vertices the proper $k$-colorings of $G$, with edges joining colorings that differ by a single Kempe change.

Bonamy–Bousquet–Feghali–Johnson conjecture. If $G=(V,E)$ is $d$-degenerate and $k>d$ is an integer, then $\mathcal{K}_k(G)$ has diameter

$$O(|V|^2).$$

The known argument establishes connectivity and gives the weaker bound $O(d^{|V(G)|})$ on the diameter. This conjecture predicts a polynomial quadratic bound, substantially improving that exponential estimate.