The twin-width of powers of graphs with bounded tree-width

par Mauricio Yepez (University of Valparaiso)

mardi 25 nov. 2025, 16:00 → 17:00 Europe/Paris

318

Twin-width is a new graph parameter introduced by Bonnet, Kim, Thomassé and Watrigant. Graphs classes with bounded twin-width include those with bounded tree-width, clique-width, and also planar graphs and proper minor-closed classes. Moreover, they preserve most of the nice algorithmic properties of clique-width. In this work, we study the twin-width of power of graphs with bounded tree-width. This is known to be bounded but existing bounds are implicit and very large. We provide a bound of k for the twin-width of the k-th power of any tree and show that this
bound is tight. We also show that if G has tree-width at most t, then the twin-width of the k-th power of G is at most (1 + 2k ) · 2k·(t−1) .