6 papers
Clique number of tournaments
Pierre Aboulker, Guillaume Aubian, Pierre Charbit +1
Given a digraph together with an ordering of its vertices, the \emph{backedge graph} of with respect to is the undirected graph with the same ve…
(Claw, C_3)-free digraphs with unbounded dichromatic number
Guillaume Aubian, Luis Kuffner
We construct orientations of rook graphs (whose underlying graphs are claw-free) that contain no directed but have unbounded dichromatic number. This disproves a conjecture o…
Complexity Gaps between Point and Interval Temporal Graphs for some Reachability Problems
Guillaume Aubian, Filippo Brunelli, Feodor F Dragan +4
Temporal graphs arise when modeling interactions that evolve over time. They usually come in several flavors, depending on the number of parameters used to describe the temporal as…
Finding forest-orderings of tournaments is NP-complete
Pierre Aboulker, Guillaume Aubian, Raul Lopes
Given a class of (undirected) graphs , we say that a Feedback Arc Set (FAS for short) is a -FAS if the graph induced by the edges of (forgetting t…
Extension of the Gyárfás-Sumner conjecture to signed graphs
Guillaume Aubian, Allen Ibiapina, Luis Kuffner +4
The balanced chromatic number of a signed graph G is the minimum number of balanced sets that cover all vertices of G. Studying structural conditions which imply bounds on the bala…
On cuts of small chromatic number in sparse graphs
Guillaume Aubian, Marthe Bonamy, Romain Bourneuf +2
For a given integer , let denote the supremum such that every sufficiently large graph with average degree less than admits a separator $X \subseteq…