2 citations · 5 across the 7 of their papers we have counts for
10 papers
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…
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…
Temporalizing digraphs via linear-size balanced bi-trees
Stéphane Bessy, Stéphan Thomassé, Laurent Viennot
In a directed graph on vertex set , a \emph{forward arc} is an arc where . A pair is \emph{forward connected} if there is a directed pat…
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…
(P6, triangle)-free digraphs have bounded dichromatic number
Pierre Aboulker, Guillaume Aubian, Pierre Charbit +1
The dichromatic number of an oriented graph is the minimum size of a partition of its vertices into acyclic induced subdigraphs. We prove that oriented graphs with no induced direc…
Extremal Independent Set Reconfiguration
Nicolas Bousquet, Bastien Durain, Théo Pierron +1
The independent set reconfiguration problem asks whether one can transform one given independent set of a graph into another, by changing vertices one by one in such a way the inte…
A quasi-quadratic vertex Kernel for Cograph edge editing
Christophe Crespelle, Rémi Pellerin, Stéphan Thomassé
We provide a vertex kernel for cograph edge editing. This improves a cubic kernel found by Guillemot, Havet, Paul and Perez [1] which involved four reductio…