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
Graph Theory » Directed Graphs

Caccetta-Häggkvist Conjecture ★★★★

Author(s): Caccetta; Häggkvist

Conjecture   Every simple digraph of order $ n $ with minimum outdegree at least $ r $ has a cycle with length at most $ \lceil n/r\rceil $

Keywords:

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

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
add new comment