2 citations · 4 across the 15 of their papers we have counts for
19 papers
Time-Optimal APSP and Matrix Multiplication in Classes of Linear Neighborhood Complexity
Édouard Bonnet, Julien Duron, Marcin Pilipczuk +2
The notion of linear neighborhood complexity is a very general structural assumption on a graph class, covering most classes of sparse graphs such as planar graphs, graphs excludin…
Hereditary 2-WQO Graph Classes Have Bounded Clique-Width
Julien Duron, Nikolas Mählmann, Szymon Toruńczyk
A graph class is -WQO if its -labeled graphs are well-quasi-ordered under label-preserving induced subgraph embeddings. We show that every hereditary graph class that is -…
Independent Set Hardness in Graphs of Bounded Twin-Width and Low-Radius Merge-Width
Édouard Bonnet, Maël Dumas, Julien Duron
For every , Max Independent Set admits a polynomial-time -approximation algorithm on -vertex graphs of effectively bounded twin-width [Bergé et a…
Decomposing tournaments into comparability graphs
Pierre Aboulker, Logan Crew, Julien Duron +7
In this note, we introduce the \emph{partial order decomposition number} of a digraph , denoted , defined as the minimum integer such that $A(D)=A(P_1)\cup\cdots\cup…
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…
Covering graphs by isometric trees
Paul Bastide, Julien Duron, Jędrzej Hodor +2
A connected subgraph of a graph is isometric if it preserves distances. Recently, graphs admitting a vertex or edge covering by a small number of isometric paths have been studied.…
Planar induced paths via a decomposition into non-crossing ordered graphs
Julien Duron, Hugo Jacob
In any graph, the maximum size of an induced path is bounded by the maximum size of a path. However, in the general case, one cannot find a converse bound, even up to an arbitrary…
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…
Long induced paths and forbidden patterns: Polylogarithmic bounds
Julien Duron, Louis Esperet, Jean-Florent Raymond
Consider a graph with a long path . When is it the case that also contains a long induced path? This question has been investigated in general as well as within a number…
Long induced paths in sparse graphs and graphs with forbidden patterns
Julien Duron, Louis Esperet, Jean-Florent Raymond
Consider a graph with a path of order . What conditions force to also have a long induced path? As complete bipartite graphs have long paths but no long induced path…
Adjacency Labeling Schemes for Small Classes
Édouard Bonnet, Julien Duron, John Sylvester +1
A graph class admits an implicit representation if, for every positive integer , its -vertex graphs have a -bit (adjacency) labeling scheme, i.e., their vertices c…
Symmetric-Difference (Degeneracy) and Signed Tree Models
Édouard Bonnet, Julien Duron, John Sylvester +1
We introduce a dense counterpart of graph degeneracy, which extends the recently-proposed invariant symmetric difference. We say that a graph has sd-degeneracy (for symmetric-diffe…
Tight bounds on adjacency labels for monotone graph classes
Édouard Bonnet, Julien Duron, John Sylvester +2
A class of graphs admits an adjacency labeling scheme of size , if the vertices in each of its -vertex graphs can be assigned binary strings (called labels) of length $b(n…
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…
A tamed family of triangle-free graphs with unbounded chromatic number
Édouard Bonnet, Romain Bourneuf, Julien Duron +3
We construct a hereditary class of triangle-free graphs with unbounded chromatic number, in which every non-trivial graph either contains a pair of non-adjacent twins or has an edg…
On the minimum number of inversions to make a digraph -(arc-)strong
Julien Duron, Frédéric Havet, Florian Hörsch +1
The {\it inversion} of a set of vertices in a digraph consists of reversing the direction of all arcs of . We study (resp. ) whic…
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…