2 citations · 4 across the 15 of their papers we have counts for
Showing 2025Show all
3 papers · 1 filter
math.CO2025
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.…
math.CO2025
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…
cs.CC2025
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…