Édouard Bonnet

collaborators

4 papers

math.CO2026

Large Finite Point Sets Have 4 Collinear Points or a 6-Clique

Édouard Bonnet

We prove that every finite point set of size at least $1 0^{11055931}$ has four collinear points or six points that pairwise see each other. This resolves the first open case of the…

cs.CC2026

Tight Inapproximability of Max Independent Set in Triangle-Free Graphs

Édouard Bonnet

For every $ε > 0$ , it is NP-hard to $n^{1 - ε}$ -approximate Max Independent Set in $n$ -vertex graphs [Hastad '96, Zuckerman '07]. In triangle-free graphs, a simpl…

cs.DS2025

Maximum Independent Set when excluding an induced minor: $K_{1} + t K_{2}$ and $t C_{3} ⊎ C_{4}$

Ãdouard Bonnet, Julien Duron, Colin Geniet +2

Dallard, MilaniÄ, and Å torgel [arXiv '22] ask if for every class excluding a fixed planar graph $H$ as an induced minor, Maximum Independent Set can be solved in polynomial time,…

math.CO2025

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 $u$ and $v$ , each edge incident to exactly o…

Large Finite Point Sets Have 4 Collinear Points or a 6-Clique

Tight Inapproximability of Max Independent Set in Triangle-Free Graphs

Maximum Independent Set when excluding an induced minor: K1​+tK2​ and tC3​⊎C4​

Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond)

Maximum Independent Set when excluding an induced minor: $K_{1} + t K_{2}$ and $t C_{3} ⊎ C_{4}$