Édouard Bonnet

activity

20132026

most citedThe Graph Motif problem parameterized by the structure of the input graph

15 citations · 87 across the 33 of their papers we have counts for

collaborators

Showing 2026Show all

3 papers · 1 filter

cs.CC2026

Arc Kayles is PSPACE-complete

Édouard Bonnet

We show that Arc Kayles is PSPACE-complete. This solves a question raised by Schaefer in 1978.

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…