15 citations · 87 across the 33 of their papers we have counts for
7 papers · 1 filter
Twin-width V: linear minors, modular counting, and matrix multiplication
Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez +1
We continue developing the theory around the twin-width of totally ordered binary structures, initiated in the previous paper of the series. We first introduce the notion of parity…
Approximating Highly Inapproximable Problems on Graphs of Bounded Twin-Width
Pierre Bergé, Édouard Bonnet, Hugues Déprés +1
For any , we give a polynomial-time -approximation algorithm for Max Independent Set in graphs of bounded twin-width given with an -sequence.…
Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
Marthe Bonamy, Édouard Bonnet, Hugues Déprés +5
A graph is -free if it does not contain pairwise vertex-disjoint and non-adjacent cycles. We prove that "sparse" (here, not containing large complete bipartite g…
Twin-width can be exponential in treewidth
Édouard Bonnet, Hugues Déprés
For any small positive real and integer , we build a graph with a vertex deletion set of size to a tree, and twin-width greater than $2…
Twin-width VII: groups
Édouard Bonnet, Colin Geniet, Romain Tessera +1
Twin-width is a recently introduced graph parameter with applications in algorithmics, combinatorics, and finite model theory. For graphs of bounded degree, finiteness of twin-widt…
Twin-width VIII: delineation and win-wins
Édouard Bonnet, Dibyayan Chakraborty, Eun Jung Kim +3
We introduce the notion of delineation. A graph class is said delineated if for every hereditary closure of a subclass of , it holds that $\ma…
Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond)
Édouard Bonnet, O-joung Kwon, David R. Wood
In a reduction sequence of a graph, vertices are successively identified until the graph has one vertex. At each step, when identifying and , each edge incident to exactly o…