24 citations · 100 across the 34 of their papers we have counts for
29 papers · 1 filter
There are no nontrivial chordal square-complementary graphs
Pierre Aboulker, Martin Milanič, Peter Muršič +1
We study square-complementary graphs (satisfying ). We show that in such graphs, no two vertices have comparable closed neighborhoods. This implies that…
Acyclic Dichromatic Number of Tournaments: these are the Champions
Pierre Aboulker, Pierre Charbit, Samuel Coulomb +2
The acyclic dichromatic number of an oriented graph is the minimum size of a vertex-partition such that the digraphs induced by any single part are acyclic, and the oriented bipart…
Decomposing tournaments into comparability graphs
Pierre Aboulker, Logan Crew, Julien Duron +7
In this note, we introduce the \emph{partial order decomposition number} of a digraph , denoted , defined as the minimum integer such that $A(D)=A(P_1)\cup\cdots\cup…
Blow-ups and extensions of trees in tournaments
Pierre Aboulker, Frédéric Havet, William Lochet +3
A class of acyclic digraphs is linearly unavoidable if there exists a constant such that every digraph is contained in all tournaments of order…
Computing the degreewidth of a digraph is hard
Pierre Aboulker, Nacim Oijid, Robin Petit +2
Given a digraph, an ordering of its vertices defines a backedge graph, namely the undirected graph whose edges correspond to the arcs pointing backwards with respect to the order.…
Minimum acyclic number and maximum dichromatic number of oriented triangle-free graphs of a given order
Pierre Aboulker, Frédéric Havet, François Pirot +1
Let be a digraph. Its acyclic number is the maximum order of an acyclic induced subdigraph and its dichromatic number is the least integer such that $…
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…
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…
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…
Various bounds on the minimum number of arcs in a -dicritical digraph
Pierre Aboulker, Quentin Vermande
The dichromatic number of a digraph is the least integer such that can be partitioned into acyclic digraphs. A digraph is -dicritical if $\vecχ(G) = k…
On the minimum number of arcs in -dicritical oriented graphs
Pierre Aboulker, Thomas Bellitto, Frédéric Havet +1
The dichromatic number $\dic(D)$ of a digraph is the least integer such that can be partitioned into directed acyclic digraphs. A digraph is -dicritical if $\dic…
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…
Chordal directed graphs are not -bounded
Pierre Aboulker, Nicolas Bousquet, Rémi de Verclos
We show that digraphs with no transitive tournament on vertices and in which every induced directed cycle has length can have arbitrarily large dichromatic number. This ans…
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…
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…
On the dichromatic number of surfaces
Pierre Aboulker, Frédéric Havet, Kolja Knauer +1
In this paper, we give bounds on the dichromatic number of a surface , which is the maximum dichromatic number of an oriented graph embeddable on . We determine th…
Extension of Gyarfas-Sumner conjecture to digraphs
Pierre Aboulker, Pierre Charbit, Reza Naserasr
The dichromatic number of a digraph is the minimum number of colors needed to color its vertices in such a way that each color class induces an acyclic digraph. As it generaliz…
Distributed coloring in sparse graphs with fewer colors
Pierre Aboulker, Marthe Bonamy, Nicolas Bousquet +1
This paper is concerned with efficiently coloring sparse graphs in the distributed setting with as few colors as possible. According to the celebrated Four Color Theorem, planar gr…
Subdivisions in digraphs of large out-degree or large dichromatic number
Pierre Aboulker, Nathann Cohen, Fréderic Havet +3
In 1985, Mader conjectured the existence of a function such that every digraph with minimum out-degree at least contains a subdivision of the transitive tournament of or…
A new class of graphs that satisfies the Chen-Chvátal Conjecture
Pierre Aboulker, Martin Matamala, Paul Rochet +1
A well-known combinatorial theorem says that a set of n non-collinear points in the plane determines at least n distinct lines. Chen and Chvátal conjectured that this theorem exten…
Colouring graphs with constraints on connectivity
Pierre Aboulker, Nick Brettell, Frédéric Havet +2
A graph has maximal local edge-connectivity if the maximum number of edge-disjoint paths between every pair of distinct vertices and is at most . We prove Brooks…
De Bruijn-Erdős type theorems for graphs and posets
Pierre Aboulker, Guillaume Lagarde, David Malec +2
A classical theorem of De Bruijn and Erdős asserts that any noncollinear set of n points in the plane determines at least n distinct lines. We prove that an analogue of this theore…