Twin-Width of Subdivisions of Multigraphs
Jungho Ahn, Debsoumya Chakraborti, Kevin Hendrey, Sang‐il Oum · SIAM Journal on Discrete Mathematics · 2025
Abstract. For each [Formula: see text], we construct a finite set [Formula: see text] of multigraphs such that for each graph [Formula: see text] of girth at least 5 obtained from a multigraph [Formula: see text] by subdividing each edge at least two times, [Formula: see text] has twin-width at most [Formula: see text] if and only if [Formula: see text] has no minor in [Formula: see text]. This answers a question of Bergé, Bonnet, and Déprés asking for the structure of graphs [Formula: see text] such that each long subdivision of [Formula: see text] has twin-width 4. As a corollary, we show that the [Formula: see text] grid has twin-width 4, which answers a question of Schidler and Szeider.