Publications

Home Schools Computational Sciences Publications

Abstract: For each d \leq 3, we construct a finite set \scrFd 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 \scrFd. This answers a question of Berge'\, Bonnet, and De'\pre'\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.

List