31 citations · 61 across the 9 of their papers we have counts for
10 papers
Forbidding anticomplete planar minors: Induced Erdős--Pósa property and Maximum Independent Set in QP
Maria Chudnovsky, Amadeus Reinald, Stéphan Thomassé
The Erdős--Pósa theorem asserts that every graph with no disjoint cycles contains a set of vertices such that has no cycle. Robertson and Seymour…
Twin-width and polynomial kernels
Édouard Bonnet, Eun Jung Kim, Amadeus Reinald +2
We study the existence of polynomial kernels, for parameterized problems without a polynomial kernel on general graphs, when restricted to graphs of bounded twin-width. Our main re…
Twin-width IV: ordered graphs and matrices
Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez +3
We establish a list of characterizations of bounded twin-width for hereditary, totally ordered binary structures. This has several consequences. First, it allows us to show that a…
Degeneracy of -free and -free graphs with no large complete bipartite subgraphs
Marthe Bonamy, Nicolas Bousquet, Michał Pilipczuk +3
A hereditary class of graphs is \emph{-bounded} if there exists a function such that every graph satisfies , where $χ(G)…
Graphs with polynomially many minimal separators
Tara Abrishami, Maria Chudnovsky, Cemil Dibek +3
We show that graphs that do not contain a theta, pyramid, prism, or turtle as an induced subgraph have polynomially many minimal separators. This result is the best possible in the…
Edge-partitioning 3-edge-connected graphs into paths
Tereza Klimošová, Stéphan Thomassé
We show that for every l, there exists d_l such that every 3-edge-connected graph with minimum degree d_l can be edge-partitioned into paths of length l (provided that its number o…
Subdivisions in digraphs of large out-degree or large dichromatic number
Pierre Aboulker, Nathann Cohen, Fréderic Havet +3
In 1985, Mader conjectured the existence of a function such that every digraph with minimum out-degree at least contains a subdivision of the transitive tournament of or…
Realization of aperiodic subshifts and uniform densities in groups
Nathalie Aubrun, Sebastián Barbieri, Stéphan Thomassé
A theorem of Gao, Jackson and Seward, originally conjectured to be false by Glasner and Uspenskij, asserts that every countable group admits a -coloring. A direct consequence of…
Conflict Packing: an unifying technique to obtain polynomial kernels for editing problems on dense instances
Christophe Paul, Anthony Perez, Stéphan Thomassé
We develop a technique that we call Conflict Packing in the context of kernelization, obtaining (and improving) several polynomial kernels for editing problems on dense instances.…
Coloring dense graphs via VC-dimension
Tomasz Łuczak, Stéphan Thomassé
The Vapnik-Červonenkis dimension is a complexity measure of set-systems, or hypergraphs. Its application to graphs is usually done by considering the sets of neighborhoods of the v…