7 citations · 11 across the 11 of their papers we have counts for
15 papers
The coarse Erdős-Pósa theorem
Sandra Albrechtsen, Marthe Bonamy, Romain Bourneuf +1
We prove the coarse Erdős-Pósa conjecture of Georgakopoulos and Papasoglu. Informally, any graph either contains many fat cycles that are pairwise far apart, or there is a small nu…
Asymmetric Homomorphism Thresholds for Graphs of Large Odd Girth
Romain Bourneuf, Raphael Steiner, Stéphan Thomassé +1
We determine the asymmetric homomorphism threshold from graphs of odd girth at least to triangle-free graphs, showing that .…
Ramsey Obstructions to Disambiguation
Romain Bourneuf, Antonin Kiladjian, Stéphan Thomassé
A partial matrix has entries in , and a disambiguation replaces each by or . We construct partial matrices whose fully specified submatrices satisfy s…
A combinatorial framework for clustering graph states: Algorithms and hardness for rank-integrity
Romain Bourneuf, Nathan Claudet, Sang Yoon Kim +3
We introduce a new notion of distance between two graph states and on the same set of qubits. This distance is the minimum number of ancilla qubits in a gr…
Sample compression schemes for balls in structurally sparse graphs
Romain Bourneuf, Jędrzej Hodor, Piotr Micek +1
Sample compression schemes were defined by Littlestone and Warmuth (1986) as an abstraction of the structure underlying many learning algorithms. In a sample compression scheme, we…
Tree decompositions whose trees are subgraphs: An application of Simon's factorization
Romain Bourneuf, Gwenaël Joret, Piotr Micek +2
We show that every connected graph has a tree decomposition indexed by a tree such that is a subgraph of and the width of the tree decomposition is bounded from abo…
On cuts of small chromatic number in sparse graphs
Guillaume Aubian, Marthe Bonamy, Romain Bourneuf +2
For a given integer , let denote the supremum such that every sufficiently large graph with average degree less than admits a separator $X \subseteq…
A Structural Linear-Time Algorithm for Computing the Tutte Decomposition
Romain Bourneuf, Tim Planken
The block-cut tree decomposes a connected graph along its cutvertices, displaying its 2-connected components. The Tutte-decomposition extends this idea to 2-separators in 2-connect…
A Polynomial-Time Approximation Algorithm for Complete Interval Minors
Romain Bourneuf, Julien Cocquet, Chaoliang Tang +1
As shown by Robertson and Seymour, deciding whether the complete graph is a minor of an input graph is a fixed parameter tractable problem when parameterized by . From…
A Dense Neighborhood Lemma: Applications of Partial Concept Classes to Domination and Chromatic Number
Romain Bourneuf, Pierre Charbit, Stéphan Thomassé
In its Euclidean form, the Dense Neighborhood Lemma (DNL) asserts that if is a finite set of points of such that for each the ball intersects…
On polynomial degree-boundedness
Romain Bourneuf, Matija Bucić, Linda Cook +1
We prove a conjecture of Bonamy, Bousquet, Pilipczuk, Rzążewski, Thomassé, and Walczak, that for every graph , there is a polynomial such that for every positive integer …
Factoring Pattern-Free Permutations into Separable ones
Édouard Bonnet, Romain Bourneuf, Colin Geniet +1
We show that for any permutation there exists an integer such that every permutation avoiding as a pattern is a product of at most separable permutations. In ot…
A tamed family of triangle-free graphs with unbounded chromatic number
Édouard Bonnet, Romain Bourneuf, Julien Duron +3
We construct a hereditary class of triangle-free graphs with unbounded chromatic number, in which every non-trivial graph either contains a pair of non-adjacent twins or has an edg…
Bounded twin-width graphs are polynomially -bounded
Romain Bourneuf, Stéphan Thomassé
We show that every graph with twin-width has chromatic number for some integer , where denotes the clique number. This extends a quasi-polynomial bound fr…
PPP-Completeness and Extremal Combinatorics
Romain Bourneuf, Lukáš Folwarczný, Pavel Hubáček +2
Many classical theorems in combinatorics establish the emergence of substructures within sufficiently large collections of objects. Well-known examples are Ramsey's theorem on mono…