ABOULKER , Pierre

A wheel is a graph formed by a chordless cycle and a vertex that has at least three neighbors in the cycle. We prove that every 3-connected graph that does not contain a wheel as a subgraph is in fact minimally 3-connected. We prove that every graph that does not contain a wheel as a subgraph is 3-colorable.

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 the asymptotic behaviour of − → χ (Σ) by showing that there exist constants a1 and a2 such that, a1 √ −c log(−c) ≤ − → χ (Σ) ≤ a2 √ −c log(−c) for every surface Σ with Euler...

In this paper, we give bounds on the dichromatic number $\vec{\chi}(\Sigma)$ of a surface $\Sigma$, which is the maximum dichromatic number of an oriented graph embeddable on $\Sigma$. We determine the asymptotic behaviour of $\vec{\chi}(\Sigma)$ by showing that there exist constants $a_1$ and $a_2$ such that, $ a_1\frac{\sqrt{-c}}{\log(-c)}...

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 the asymptotic behaviour of χ(Σ) by showing that there exist constants a 1 and a 2 such that, a 1 √ −c log(−c) χ(Σ) a 2 √ −c log(−c) for every surface Σ with Euler characteristic...

The dichromatic number ⃗ χ(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 ⃗ χ(D) = k and each proper subgraph D ′ of D satisfies ⃗ χ(D) ≤ k − 1. An oriented graph is a digraph with no directed cycle of length 2. For integers k and n, we denote by o k (n) the...

The dichromatic number $\vec{\chi }(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 $\vec{\chi }(D) = k$ and each proper subgraph $D^{\prime }$ of $D$ satisfies $\vec{\chi }(D^{\prime }) \leq k-1$. An oriented graph is a digraph with no directed...

A graph G has maximal local edge-connectivity k if the maximum number of edge-disjoint paths between every pair of distinct vertices x and y is at most k. We prove Brooks-type theorems for k-connected graphs with maximal local edge-connectivity k, and for any graph with maximal local edge-connectivity 3. We also consider several related graph...

A famous conjecture of Gyárfás and Sumner states for any tree T and integer k, if the chromatic number of a graph is large enough, either the graph contains a clique of size k or it contains T as an induced subgraph. We discuss some results and open problems about extensions of this conjecture to oriented graphs. We conjecture that for every...

A famous conjecture of Gyárfás and Sumner states for any tree T and integer k, if the chromatic number of a graph is large enough, either the graph contains a clique of size k or it contains T as an induced subgraph. We discuss some results and open problems about extensions of this conjecture to oriented graphs. We conjecture that for every...

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 existence of f (5) remains unknown. In this paper, we show that if D is an oriented path, or an in-arborescence...

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 existence of f (5) remains unknown. In this paper, we show that if D is an oriented path, or an in-arborescence...

A class of acyclic digraphs $\mathscr{C}$ is linearly unavoidable if there exists a constant $c$ such that every digraph $D\in \mathscr{C}$ is contained in all tournaments of order $c\cdot |V(D)|$. The class of all acyclic digraphs is not linearly avoidable, and Fox, He, and Widgerson recently showed that this is not even the case for acyclic...