Twin-width of subdivisions of multigraphs

06/08/2023

∙

by   Jungho Ahn, et al.

∙

0

∙

share

For each d≤3, we construct a finite set F_d of multigraphs such that for each graph H of girth at least 5 obtained from a multigraph G by subdividing each edge at least two times, H has twin-width at most d if and only if G has no minor in F_d. This answers a question of Bergé, Bonnet, and Déprés asking for the structure of graphs G such that each long subdivision of G has twin-width 4. As a corollary, we show that the 7×7 grid has twin-width 4, which answers a question of Schidler and Szeider.