Graph Theory » Directed Graphs

Antidirected trees in digraphs ★★

Author(s): Addario-Berry; Havet; Linhares Sales; Reed; Thomassé

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
add new comment
Graph Theory » Directed Graphs » Tournaments

Decomposing an even tournament in directed paths. ★★★

Author(s): Alspach; Mason; Pullman

Conjecture   Every tournament $ D $ on an even number of vertices can be decomposed into $ \sum_{v\in V}\max\{0,d^+(v)-d^-(v)\} $ directed paths.

Keywords:

Posted by fhavet
updated February 26th, 2013
add new comment
Graph Theory » Directed Graphs

Oriented trees in n-chromatic digraphs ★★★

Author(s): Burr

Conjecture   Every digraph with chromatic number at least $ 2k-2 $ contains every oriented tree of order $ k $ as a subdigraph.

Keywords:

Posted by fhavet
updated February 25th, 2013
add new comment