Linear recoloring diameter of degenerate chordal graphs and bounded treewidth graphs

Let G be a graph on n vertices and t an integer. The reconfiguration graph of G, denoted by Rₜ(G), consists of all t-colorings of G and two t-colorings are adjacent if they differ on exactly one vertex. The t-recoloring diameter of G is the diameter of Rₜ(G). For a d-degenerate graph G, Rₜ(G) is connected when t ≥ d+2~(Dyer et al., 2006). Furthermore, the t-recoloring diameter is O(n²) when t ≥ 3(d+1)/2~(Bousquet et al., 2022), and it is $O(n)$ when t ≥ 2d+2~(Bousquet and Perarnau, 2016). For a d-degenerate and chordal graph G, the t-recoloring diameter of G is O(n²) when t ≥ d+2~(Bonamy et al. 2014). If G is a graph of treewidth at most k, then G is also k-degenerate, and the previous results hold. Moreover, when t ≥ k+2, the t-recoloring diameter is O(n²)~(Bonamy and Bousquet, 2013). When $k=2$, the t-recoloring diameter of G is linear when t ≥ 5~(Bartier, Bousquet and Heinrich, 2021) and the result is tight. In this paper, we prove that if G is d-degenerate and chordal, then the t-recoloring diameter of G is $O(n)$ when t ≥ 2d+1. Moreover, if the treewidth of G is at most k, then the t-recoloring diameter is $O(n)$ when t ≥ 2k+1. This result is a generalization of the previous results on graphs of treewidth at most two.