1 citations · 1 across the 1 of their papers we have counts for
5 papers
Diameter of the inversion graph
Frédéric Havet, Florian Hörsch, Clément Rambaud
In an oriented graph , the inversion of a subset of vertices consists in reversing the orientation of all arcs with both endvertices in . The inversion graph of a l…
The 3-dicritical semi-complete digraphs
Frédéric Havet, Florian Hörsch, Lucas Picasarri-Arrieta
A digraph is -dicritical if it cannot be vertex-partitioned into two sets inducing acyclic digraphs, but each of its proper subdigraphs can. We give a human-readable proof that…
Complexity of (arc)-connectivity problems involving arc-reversals or deorientations
Jørgen Bang-Jensen, Florian Hörsch, Matthias Kriesell
By a well known theorem of Robbins, a graph has a strongly connected orientation if and only if is 2-edge-connected and it is easy to find, in linear time, either a cut edg…
Decompositions into two linear forests of bounded lengths
Rutger Campbell, Florian Hörsch, Benjamin Moore
For some , we call a linear forest -bounded if each of its components has at most edges. We will say a -bounded linear forest…
A note on 2-vertex-connected orientations
Florian Hörsch, Zoltán Szigeti
We consider two possible extensions of a theorem of Thomassen characterizing the graphs admitting a 2-vertex-connected orientation. First, we show that the problem of deciding whet…