Pith. sign in

Twin-width of subdivisions of multigraphs

1 Pith paper cite this work. Polarity classification is still indexing.

1 Pith paper citing it
abstract

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

fields

cs.DM 1

years

2025 1

verdicts

CONDITIONAL 1

representative citing papers

Twin-width one

cs.DM · 2025-01-02 · conditional · novelty 8.0

Graphs of twin-width at most 1 are exactly a subclass of permutation graphs, can be recognized in linear time, and distance-hereditary graphs have twin-width 0, 1, or 2 according to their split decomposition.

citing papers explorer

Showing 1 of 1 citing paper.

  • Twin-width one cs.DM · 2025-01-02 · conditional · none · ref 1 · internal anchor

    Graphs of twin-width at most 1 are exactly a subclass of permutation graphs, can be recognized in linear time, and distance-hereditary graphs have twin-width 0, 1, or 2 according to their split decomposition.