activity
20232026
most citedA tamed family of triangle-free graphs with unbounded chromatic number

2 citations · 4 across the 15 of their papers we have counts for

collaborators
Showing cs.CCShow all

3 papers · 1 filter

cs.CC2026

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…

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…

cs.CC2023★ 1 cited

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…