P Aboulker
YOU?
Author Swipe
View article: ($\overrightarrow{P_6}$, triangle)-Free Digraphs Have Bounded Dichromatic Number
($\overrightarrow{P_6}$, triangle)-Free Digraphs Have Bounded Dichromatic Number Open
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 directed path on six vertices and no triangle have bounded dichr…
View article: Computing the degreewidth of a digraph is hard
Computing the degreewidth of a digraph is hard Open
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. The degreewidth of a digraph is the minimum over all orderi…
View article: On the Minimum Number of Arcs in \(\boldsymbol{k}\)-Dicritical Oriented Graphs
On the Minimum Number of Arcs in \(\boldsymbol{k}\)-Dicritical Oriented Graphs Open
International audience
View article: Finding forest-orderings of tournaments is NP-complete
Finding forest-orderings of tournaments is NP-complete Open
Given a class of (undirected) graphs $\mathcal{C}$, we say that a Feedback Arc Set (FAS for short) $F$ is a $\mathcal{C}$-FAS if the graph induced by the edges of $F$ (forgetting their orientations) belongs to $\mathcal{C}$. We show that d…
View article: Various Bounds on the Minimum Number of Arcs in a $k$-Dicritical Digraph
Various Bounds on the Minimum Number of Arcs in a $k$-Dicritical Digraph Open
The dichromatic number $\vec{\chi}(G)$ of a digraph $G$ is the least integer $k$ such that $G$ can be partitioned into $k$ acyclic digraphs. A digraph is $k$-dicritical if $\vec{\chi}(G) = k$ and each proper subgraph $H$ of $G$ satisfies $…
View article: Digraph Colouring and Arc-Connectivity
Digraph Colouring and Arc-Connectivity Open
The dichromatic number $\vecχ(D)$ of a digraph $D$ is the minimum size of a partition of its vertices into acyclic induced subgraphs. We denote by $λ(D)$ the maximum local edge connectivity of a digraph $D$. Neumann-Lara proved that for ev…
View article: (P6, triangle)-free digraphs have bounded dichromatic number
(P6, triangle)-free digraphs have bounded dichromatic number Open
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 directed path on six vertices and no triangle have bounded dichr…
View article: Vizing's and Shannon's Theorems for Defective Edge Colouring
Vizing's and Shannon's Theorems for Defective Edge Colouring Open
We call a multigraph $(k,d)$-edge colourable if its edge set can be partitioned into $k$ subgraphs of maximum degree at most $d$ and denote as $\chi'_{d}(G)$ the minimum $k$ such that $G$ is $(k,d)$-edge colourable. We prove that for every…
View article: Various bounds on the minimum number of arcs in a $k$-dicritical digraph
Various bounds on the minimum number of arcs in a $k$-dicritical digraph Open
The dichromatic number $\vecχ(G)$ of a digraph $G$ is the least integer $k$ such that $G$ can be partitioned into $k$ acyclic digraphs. A digraph is $k$-dicritical if $\vecχ(G) = k$ and each proper subgraph $H$ of $G$ satisfies $\vecχ(H) \…
View article: On the minimum number of arcs in $k$-dicritical oriented graphs
On the minimum number of arcs in $k$-dicritical oriented graphs Open
The dichromatic number $\dic(D)$ of a digraph $D$ is the least integer $k$ such that $D$ can be partitioned into $k$ directed acyclic digraphs. A digraph is $k$-dicritical if $\dic(D) = k$ and each proper subgraph $D'$ of $D$ satisfies $\d…
View article: Heroes in oriented complete multipartite graphs
Heroes in oriented complete multipartite graphs Open
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 $\mathcal C$, a digraph $H$ is a hero in $\mc C$ if $H$-free digraphs of $\mathcal C$ have bou…
View article: Heroes in orientations of chordal graphs
Heroes in orientations of chordal graphs Open
We characterize all digraphs $H$ such that orientations of chordal graphs with no induced copy of $H$ have bounded dichromatic number.
View article: Chordal directed graphs are not $χ$-bounded
Chordal directed graphs are not $χ$-bounded Open
We show that digraphs with no transitive tournament on $3$ vertices and in which every induced directed cycle has length $3$ can have arbitrarily large dichromatic number. This answers to the negative a question of Carbonero, Hompe, Moore,…
View article: Vizing's and Shannon's Theorems for defective edge colouring
Vizing's and Shannon's Theorems for defective edge colouring Open
We call a multigraph $(k,d)$-edge colourable if its edge set can be partitioned into $k$ subgraphs of maximum degree at most $d$ and denote as $χ'_{d}(G)$ the minimum $k$ such that $G$ is $(k,d)$-edge colourable. We prove that for every in…
View article: Four proofs of the directed Brooks' Theorem
Four proofs of the directed Brooks' Theorem Open
We give four new proofs of the directed version of Brook's Theorem and an NP-completeness result.
View article: On the dichromatic number of surfaces
On the dichromatic number of surfaces Open
In this paper, we give bounds on the dichromatic number $\vecχ(Σ)$ of a surface $Σ$, which is the maximum dichromatic number of an oriented graph embeddable on $Σ$. We determine the asymptotic behaviour of $\vecχ(Σ)$ by showing that there …
View article: Graphs with no induced house nor induced hole have the de\n Bruijn-Erd\\H{o}s property
Graphs with no induced house nor induced hole have the de\n Bruijn-Erd\\H{o}s property Open
A set of n points in the plane which are not all collinear defines at least n\ndistinct lines. Chen and Chv\\'atal conjectured in 2008 that a similar result\ncan be achieved in the broader context of finite metric spaces. This conjecture\n…
View article: Issue Information
Issue Information Open
The 2-surviving rate of planar graphs with average degree lower than 9 -
View article: Distributed coloring in sparse graphs with fewer colors
Distributed coloring in sparse graphs with fewer colors Open
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 graphs can be colored with at most 4 colors, and the proof gi…
View article: Subdivisions in digraphs of large out-degree or large dichromatic number
Subdivisions in digraphs of large out-degree or large dichromatic number Open
In 1985, Mader conjectured the existence of a function $f$ such that every digraph with minimum out-degree at least $f(k)$ contains a subdivision of the transitive tournament of order $k$. This conjecture is still completely open, as the e…