Graph Theory

Minimum number of arc-disjoint transitive subtournaments of order 3 in a tournament ★★

Author(s): Yuster

Conjecture   If $ T $ is a tournament of order $ n $, then it contains $ \left \lceil n(n-1)/6 - n/3\right\rceil $ arc-disjoint transitive subtournaments of order 3.

Keywords:

Posted by fhavet
updated May 21st, 2013
add new comment
Combinatorics » Matrices

Difference between neighbors in a matrix ★

Author(s): Vadim Lioubimov

Conjecture   Any $ n\times n $ matrix with different integer entries has two neighboring entries $ a,b $ with $ |a-b|\ge n $.

Keywords:

Posted by Vadim Lioubimov
updated July 20th, 2013
4 comments
Graph Theory » Directed Graphs

Arc-disjoint directed cycles in regular directed graphs ★★

Author(s): Alon; McDiarmid; Molloy

Conjecture   If $ G $ is a $ k $-regular directed graph with no parallel arcs, then $ G $ contains a collection of $ {k+1 \choose 2} $ arc-disjoint directed cycles.

Keywords:

Posted by fhavet
updated May 17th, 2013
add new comment