6 papers · 1 filter
Coloring Hardness on Low Twin-Width Graphs
Édouard Bonnet
As the class of graphs of twin-width at most 4 contains every finite subgraph of the infinite grid and every graph obtained by subdividing each edge of an -vertex…
Excluding a Forest Induced Minor
Édouard Bonnet, Benjamin Duhamel, Robert Hickingbotham
In the first paper of the Graph Minors series [JCTB '83], Robertson and Seymour proved the Forest Minor theorem: the -minor-free graphs have bounded pathwidth if and only if …
Separator Theorem for Minor-Free Graphs in Linear Time
Édouard Bonnet, Tuukka Korhonen, Hung Le +2
The planar separator theorem by Lipton and Tarjan [FOCS '77, SIAM Journal on Applied Mathematics '79] states that any planar graph with vertices has a balanced separator of siz…
Every Graph is Essential to Large Treewidth
Bogdan Alecu, Édouard Bonnet, Pedro Bureo Villafana +1
We show that for every graph , there is a hereditary weakly sparse graph class of unbounded treewidth such that the -free (i.e., excluding as an induced su…
Induced Disjoint Paths Without an Induced Minor
Pierre Aboulker, Édouard Bonnet, Timothé Picavet +1
We exhibit a new obstacle to the nascent algorithmic theory for classes excluding an induced minor. We indeed show that on the class of string graphs -- which avoids the 1-subdivis…
Mim-Width is paraNP-complete
Benjamin Bergougnoux, Édouard Bonnet, Julien Duron
We show that it is NP-hard to distinguish graphs of linear mim-width at most 1211 from graphs of sim-width at least 1216. This implies that Mim-Width, Sim-Width, One-Sided Mim-Widt…