115 citations · 430 across the 53 of their papers we have counts for
6 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…
Graphs with large chromatic number induce -cycles
Marthe Bonamy, Pierre Charbit, Stéphan Thomassé
Answering a question of Kalai and Meshulam, we prove that graphs without induced cycles of length have bounded chromatic number. This implies the very first case of a much bro…
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…
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…
Isolating highly connected induced subgraphs
Irena Penev, Stéphan Thomassé, Nicolas Trotignon
We prove that any graph of minimum degree greater than has a -connected induced subgraph such that the number of vertices of that have neighbors outside…
A note on the minimum distance of quantum LDPC codes
Nicolas Delfosse, Zhentao Li, Stéphan Thomassé
We provide a new lower bound on the minimum distance of a family of quantum LDPC codes based on Cayley graphs proposed by MacKay, Mitchison and Shokrollahi. Our bound is exponentia…