15 citations · 87 across the 33 of their papers we have counts for
6 papers · 1 filter
Factoring Pattern-Free Permutations into Separable ones
Édouard Bonnet, Romain Bourneuf, Colin Geniet +1
We show that for any permutation there exists an integer such that every permutation avoiding as a pattern is a product of at most separable permutations. In ot…
Small But Unwieldy: A Lower Bound on Adjacency Labels for Small Classes
Édouard Bonnet, Julien Duron, John Sylvester +2
We show that for any natural number , there is a constant and a subgraph-closed class having, for any natural , at most graphs on vertices up to isomorphism, bu…
Stretch-width
Édouard Bonnet, Julien Duron
We introduce a new parameter, called stretch-width, that we show sits strictly between clique-width and twin-width. Unlike the reduced parameters [BKW '22], planar graphs and polyn…
Cutting Barnette graphs perfectly is hard
Édouard Bonnet, Dibyayan Chakraborty, Julien Duron
A perfect matching cut is a perfect matching that is also a cutset, or equivalently a perfect matching containing an even number of edges on every cycle. The corresponding algorith…
Maximum Independent Set when excluding an induced minor: and
Édouard Bonnet, Julien Duron, Colin Geniet +2
Dallard, Milanič, and Štorgel [arXiv '22] ask if for every class excluding a fixed planar graph as an induced minor, Maximum Independent Set can be solved in polynomial time, a…
Neighbourhood complexity of graphs of bounded twin-width
Édouard Bonnet, Florent Foucaud, Tuomo Lehtilä +1
We give essentially tight bounds for, , the maximum number of distinct neighbourhoods on a set of vertices in a graph with twin-width at most~. Using the celebra…