Autor:	Ahn, Jungho, Chakraborti, Debsoumya, Hendrey, Kevin, Oum, Sang-il
Rok vydání:	2023
Předmět:	Mathematics - Combinatorics Computer Science - Discrete Mathematics 05C35 05C75
Druh dokumentu:	Working Paper
Popis:	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. Comment: 46 pages, 8 figures, 1 table
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2306.05334 Zobrazit plný text záznamu View this record from Arxiv