Linear recoloring diameter of Halin graphs

For a graph G and a positive integer k , let ℛ 𝑘 ⁡ ( 𝐺 ) denote the k -reconfiguration graph of the proper k -colorings of G , where two colorings are adjacent if they differ on exactly one vertex. Cereceda conjectured that, for every d -degenerate n -vertex graph G , the diameter of ℛ 𝑘 ⁡ ( 𝐺 ) is O ( n 2 ) whenever 𝑘 ⁢ 𝑑 + 2 . Bonamy and Bousquet proved the corresponding quadratic bound for graphs of treewidth t when 𝑘 ⁢ 𝑡 + 2 , and hence a quadratic bound for the 5-recoloring diameter of Halin graphs. In this paper, we improve this quadratic bound to a linear one. More precisely, we prove that every n -vertex Halin graph G satisfies d i a m ⁡ ( ℛ 𝑘 ⁡ ( 𝐺 ) ) ⁢ 4 ⁢ 𝑛 − 1 for every k 5. In fact, the bound can be improved to 4 ⁢ 𝑛 − 3 when the outer cycle has even length. Moreover, the threshold k 5 is best possible.