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