Importance: High ✭✭✭
Author(s): Thomassé, Stéphan
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.


* indicates original appearance(s) of problem.

Reply

Comments are limited to a maximum of 1000 characters.
More information about formatting options