Graph Theory » Directed Graphs

Long directed cycles in diregular digraphs ★★★

Author(s): Jackson

Conjecture   Every strong oriented graph in which each vertex has indegree and outdegree at least $ d $ contains a directed cycle of length at least $ 2d+1 $.

Keywords:

Posted by fhavet
updated March 1st, 2013
add new comment
Graph Theory » Directed Graphs

Splitting a digraph with minimum outdegree constraints ★★★

Author(s): Alon

Problem   Is there a minimum integer $ f(d) $ such that the vertices of any digraph with minimum outdegree $ d $ can be partitioned into two classes so that the minimum outdegree of the subgraph induced by each class is at least $ d $?

Keywords:

Posted by fhavet
updated March 1st, 2013
add new comment
Graph Theory

Stable set meeting all longest directed paths. ★★

Author(s): Laborde; Payan; Xuong N.H.

Conjecture   Every digraph has a stable set meeting all longest directed paths

Keywords:

Posted by fhavet
updated March 1st, 2013
add new comment
Graph Theory » Directed Graphs

Ádám's Conjecture ★★★

Author(s): Ádám

Conjecture   Every digraph with at least one directed cycle has an arc whose reversal reduces the number of directed cycles.

Keywords:

Posted by fhavet
updated March 1st, 2013
add new comment