3 citations · 7 across the 15 of their papers we have counts for
17 papers
Clique Number of Tournaments II
Guillaume Aubian, Samuel Coulomb
The directed clique number of a tournament is the minimum, over all orderings of the vertices of , of the clique number of the graph whose edges are the arcs that…
(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…
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…
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…
Computing the clique number of tournaments
Guillaume Aubian
The clique number of a tournament is the maximum clique number of a graph formed by keeping backwards arcs in an ordering of its vertices. We study the time complexity of computing…
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…
Colouring Digraphs
Guillaume Aubian
The aim of this thesis is to investigate how the structure of a digraph affects its dichromatic number and to extend various results on undirected colouring to digraphs. In the fir…
Digraph Colouring and Arc-Connectivity
Pierre Aboulker, Guillaume Aubian, Pierre Charbit
The dichromatic number of a digraph is the minimum size of a partition of its vertices into acyclic induced subgraphs. We denote by the maximum local edge con…
(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…
Problems, proofs, and disproofs on the inversion number
Guillaume Aubian, Frédéric Havet, Florian Hörsch +4
The {\it inversion} of a set of vertices in a digraph consists in reversing the direction of all arcs of . The {\it inversion number} of an oriented grap…
Heroes in orientations of chordal graphs
Pierre Aboulker, Guillaume Aubian, Raphael Steiner
We characterize all digraphs such that orientations of chordal graphs with no induced copy of have bounded dichromatic number.
Vizing's and Shannon's Theorems for defective edge colouring
Pierre Aboulker, Guillaume Aubian, Chien-Chung Huang
We call a multigraph -edge colourable if its edge set can be partitioned into subgraphs of maximum degree at most and denote as the minimum such that…
Heroes in oriented complete multipartite graphs
Pierre Aboulker, Guillaume Aubian, Pierre Charbit
The dichromatic number of a digraph is the minimum size of a partition of its vertices into acyclic induced subgraphs. Given a class of digraphs , a digraph is a he…
Four proofs of the directed Brooks' Theorem
Pierre Aboulker, Guillaume Aubian
We give four new proofs of the directed version of Brook's Theorem and an NP-completeness result.
Decomposing and colouring some locally semicomplete digraphs
Pierre Aboulker, Guillaume Aubian, Pierre Charbit
A digraph is semicomplete if any two vertices are connected by at least one arc and is locally semicomplete if the out-neighbourhood and the in-neighbourhood of any vertex induce a…