2025/09/18 by Wang, Yichen, Lu, Mei
#05C15 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2509.15456
Let G be a graph on n vertices and t an integer. The reconfiguration graph of G, denoted by Rt(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 Rt(G). For a d-degenerate graph G, Rt(G) is connected when t ≥ d+2~(Dyer et al., 2006). Furthermore, the t-recoloring diameter is O(n2) 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(n2) 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(n2)~(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.