Twin-width of subdivisions of multigraphs

Abstract

For each $d\le 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\times 7$ grid has twin-width $4$, which answers a question of Schidler and Szeider.

arXiv comment46 pages, 8 figures, 1 table

References in corpus (3)

• Grid Induced Minor Theorem for Graphs of Small Degree
• Bounds for the Twin-width of Graphs
• Twin-width of random graphs