13 citations · 19 across the 9 of their papers we have counts for
4 papers · 1 filter
Tight Inapproximability of Max Independent Set in Triangle-Free Graphs
Édouard Bonnet
For every , it is NP-hard to -approximate Max Independent Set in -vertex graphs [Hastad '96, Zuckerman '07]. In triangle-free graphs, a simpl…
Grundy Coloring & friends, Half-Graphs, Bicliques
Pierre Aboulker, Édouard Bonnet, Eun Jung Kim +1
The first-fit coloring is a heuristic that assigns to each vertex, arriving in a specified order , the smallest available color. The problem Grundy Coloring asks how many colors…
Metric Dimension Parameterized by Treewidth
Édouard Bonnet, Nidhi Purohit
A resolving set of a graph is a subset of its vertices such that no two vertices of have the same distance vector to . The Metric Dimension problem asks for a resolv…
On the Complexity of Connection Games
Édouard Bonnet, Florian Jamain, Abdallah Saffidine
In this paper, we study three connection games among the most widely played: Havannah, Twixt, and Slither. We show that determining the outcome of an arbitrary input position is PS…