Thomassé, Stéphan

Directed path of length twice the minimum outdegree ★★★

Author(s): Thomassé

Conjecture Every oriented graph with minimum outdegree $k$ contains a directed path of length $2k$ .

Keywords:

Posted by fhavet
updated February 28th, 2013

An antidirected tree is an orientation of a tree in which every vertex has either indegree 0 or outdergree 0.

Conjecture Let $D$ be a digraph. If $|A(D)| > (k-2) |V(D)|$ , then $D$ contains every antidirected tree of order $k$ .

Keywords:

Posted by fhavet
updated February 26th, 2013