LOCHET , William

The main purpose of the thesis was to exhibit sufficient conditions on digraphs to find subdivisions of complex structures. While this type of question is pretty well understood in the case of (undirected) graphs, few things are known for the case of directed graphs (also called digraphs). The most notorious conjecture is probably the one due...

We prove the existence of a function $h(k)$ such that every simple digraph with minimum outdegree greater than $h(k)$ contains an immersion of the transitive tournament on k vertices. This solves a conjecture of Devos, McDonald, Mohar and Scheide.

Caro, West, and Yuster studied how r-uniform hypergraphs can be oriented in such a way that (generalizations of) indegree and outdegree are as close to each other as can be hoped. They conjectured an existence result of such orientations for sparse hypergraphs, of which we present a proof.

A very nice result of Bárány and Lehel asserts that every finite subset X or can be covered by X-boxes (i.e. each box has two antipodal points in X). As shown by Gyárfás and Pálvőlgyi this result would follow from the following conjecture: If a tournament admits a partition of its arc set into k quasi-orders, then its domination number is...

A (k 1 + k 2)-bispindle is the union of k 1 (x, y)-dipaths and k 2 (y, x)-dipaths, all these dipaths being pairwise internally disjoint. Recently, Cohen et al. showed that for every (2 + 0)-bispindle B, there exists an integer k such that every strongly connected digraph with chromatic number greater than k contains a subdivision of B. We...

An oriented cycle is an orientation of a undirected cycle. We first show that for any oriented cycle C, there are digraphs containing no subdivision of C (as a subdigraph) and arbitrarily large chromatic number. In contrast, we show that for any C a cycle with two blocks, every strongly connected digraph with sufficiently large chromatic number...

An {\it oriented cycle} is an orientation of a undirected cycle.We first show that for any oriented cycle $C$, there are digraphs containing no subdivision of $C$ (as a subdigraph) and arbitrarily large chromatic number.In contrast, we show that for any $C$ is a cycle with two blocks, every strongly connected digraph with sufficiently large...

A (k1 + k2)-bispindle is the union of k1 (x, y)-dipaths and k2 (y, x)-dipaths, all these dipaths being pairwise internally disjoint. Recently, Cohen et al. showed that for every (1, 1)- bispindle B, there exists an integer k such that every strongly connected digraph with chromatic number greater than k contains a subdivision of B. We...

Extended Abstract The chromatic number χ(D) of a digraph D is the chromatic number of its underlying graph. An oriented cycle is an orientation of a undirected cycle. We first show that for any oriented cycle C, there are digraphs containing no subdivision of C (as a subdigraph) and arbitrarily large chromatic number. In contrast, we show that...

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...

In this short note we prove that every tournament contains the k -th power of a directed path of linear length. This improves upon recent results of Yuster and of Girão. We also give a complete solution for this problem when k =2, showing that there is always a square of a directed path of length, which is best possible.