33 citations · 242 across the 67 of their papers we have counts for
8 papers · 1 filter
VC-dimension and Erdős-Pósa property
Nicolas Bousquet, Stéphan Thomassé
Let be a graph. A -neighborhood in is a set of vertices consisting of all the vertices at distance at most from some vertex of . The hypergraph on vertex se…
Fast Recoloring of Sparse Graphs
Nicolas Bousquet, Guillem Perarnau
In this paper, we show that for every graph of maximum average degree bounded away from , any -coloring can be transformed into any other one within a polynomial number o…
On the practical interest of discrete Inverse Polya and Weibull-1 models in industrial reliability studies
Alberto Pasanisi, Côme Roero, Nicolas Bousquet +1
Engineers often cope with the problem of assessing the lifetime of industrial components, under the basis of observed industrial feedback data. Usually, lifetime is modelled as a c…
The Erdős-Hajnal Conjecture for Long Holes and Anti-holes
Marthe Bonamy, Nicolas Bousquet, Stéphan Thomassé
Erdős and Hajnal conjectured that, for every graph , there exists a constant such that every graph on vertices which does not contain any induced copy of has a…
A Near-Optimal Mechanism for Impartial Selection
Nicolas Bousquet, Sergey Norin, Adrian Vetta
We examine strategy-proof elections to select a winner amongst a set of agents, each of whom cares only about winning. This impartial selection problem was introduced independently…
Identifying codes in hereditary classes of graphs and VC-dimension
Nicolas Bousquet, Aurélie Lagoutte, Zhentao Li +2
An identifying code of a graph is a subset of its vertices such that every vertex of the graph is uniquely identified by the set of its neighbours within the code. We show a dichot…