7 citations · 11 across the 11 of their papers we have counts for
6 papers · 1 filter
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…