Linear recoloring diameter of degenerate chordal graphs and bounded treewidth graphs
Yichen Wang, Mei Lu · Discrete Mathematics · 2026
Let G be a graph on n vertices and t an integer. The reconfiguration graph of G , denoted by R t ( 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 t ( G ) . For a d -degenerate graph G , R t ( G ) is connected when t ≥ d + 2 (Dyer, Flaxman, Frieze and Vigoda, 2006). Furthermore, the t -recoloring diameter is O ( n 2 ) when t ≥ 3 ( d + 1 ) / 2 (Bousquet and Heinrich, 2022), and it is O ( n ) when t ≥ 2 d + 2 (Bousquet and Perarnau, 2016). For a d -degenerate and chordal graph G , the t -recoloring diameter of G is O ( n 2 ) when t ≥ d + 2 (Bonamy, Johnson, Lignos, Patel and Paulusma, 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 2 ) (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 ≥ 2 d + 1 . Moreover, if the treewidth of G is at most k , then the t -recoloring diameter is O ( n ) when t ≥ 2 k + 1 . This result is a generalization of the previous results on graphs of treewidth at most two.