Pith. sign in

REVIEW 1 cited by

Twin-width of subdivisions of multigraphs

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2306.05334 v2 pith:JJSGBVOC submitted 2023-06-08 math.CO cs.DM

Jungho Ahn , Debsoumya Chakraborti , Kevin Hendrey , Sang-il Oum This is my paper · ORCID
classification math.COcs.DM
keywords twin-widthanswersleastmultigraphsquestionaskingbergbonnet
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
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.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Twin-width one

    cs.DM 2025-01 conditional novelty 8.0 of 10

    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.

Pith tools