Twin-width of subdivisions of multigraphs

arXiv2306.05334MaRDI QIDQ6439686FDOQ6439686

Authors: Jung-Ho Ahn, Debsoumya Chakraborti, Kevin Hendrey, Sang-Il Oum 

Publication date: 8 June 2023

Abstract: For each $dleq3$, 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'{e}, Bonnet, and D'{e}pr'{e}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 $7imes7$ grid has twin-width $4$, which answers a question of Schidler and Szeider.

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Structural characterization of families of graphs (05C75)

This page was built for publication: Twin-width of subdivisions of multigraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6439686)