Open Problem Garden

Importance: High ✭✭✭

Author(s):

Subject:	Graph Theory
	» Directed Graphs

Keywords:

Recomm. for undergrads: no

Posted	by:	fhavet
	on:	February 28th, 2013

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

In fact, Thomassé made the following stronger conjecture which implies the celebrated Cacetta-Häggkvist Conjecture.

Conjecture Every digraph with minimum outdegree $k$ and directed girth $g$ , contains a directed path of length $(g-1)k$ .

This conjecture holds easily when $g=2$ . For $g=3$ it is the above conjecture which is still open.

Bibliography

* indicates original appearance(s) of problem.