8 papers
Moderately beyond clique-width: reduced component max-leaf and related parameters
Ãdouard Bonnet, Yeonsu Chang, Julien Duron +2
Reduced parameters [BKW, JCTB '26; BKRT, SODA '22] are defined via contraction sequences. Based on this framework, we introduce the reduced component max-leaf, denoted by $\operato…
Coarse Balanced Separators in Fat-Minor-Free Graphs
Ãdouard Bonnet, Hung Le, Marcin Pilipczuk +1
Fat minors are a coarse analogue of graph minors where the subgraphs modeling vertices and edges of the embedded graph are required to be distant from each other, instead of just b…
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…