6 citations · 24 across the 32 of their papers we have counts for
24 papers · 1 filter
A relaxation of the Bermond-Thomassen conjecture
Stéphane Bessy, Matthijs Muis, Jean-Sébastien Sereni +2
The well-known Bermond-Thomassen conjecture states that every digraph of minimum out-degree at least contains vertex-disjoint directed cycles. Despite being posed in 198…
Plane Strong Connectivity Augmentation
Stéphane Bessy, Daniel Gonçalves, Amadeus Reinald +1
We investigate the problem of strong connectivity augmentation within plane oriented graphs. We show that deciding whether a plane oriented graph can be augmented with (any num…
Oriented trees in -chromatic digraphs, a subquadratic bound for Burr's conjecture
Stéphane Bessy, Daniel Gonçalves, Amadeus Reinald
In 1980, Burr conjectured that every directed graph with chromatic number contains any oriented tree of order as a subdigraph. Burr showed that chromatic number $(k-1)^2…
Dichromatic number of chordal graphs
Stéphane Bessy, Frédéric Havet, Lucas Picasarri-Arrieta
The dichromatic number of a digraph is the minimum integer such that it admits a -dicolouring, i.e. a partition of its vertices into acyclic subdigraphs. We say that a d…
Sparse vertex cutsets and the maximum degree
Stéphane Bessy, Johannes Rauch, Dieter Rautenbach +1
We show that every graph of maximum degree and sufficiently large order has a vertex cutset of order at most that induces a subgraph of maximum degree at mos…
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…