Thomassen, Carsten

Graph Theory » Directed Graphs » Tournaments

Partitionning a tournament into k-strongly connected subtournaments. ★★

Problem Let $k_1, \dots , k_p$ be positve integer Does there exists an integer $g(k_1, \dots , k_p)$ such that every $g(k_1, \dots , k_p)$ -strong tournament $T$ admits a partition $(V_1\dots , V_p)$ of its vertex set such that the subtournament induced by $V_i$ is a non-trivial $k_i$ -strong for all $1\leq i\leq p$ .

Keywords:

Posted by fhavet
updated March 15th, 2013

add new comment

Graph Theory » Directed Graphs » Tournaments

Edge-disjoint Hamilton cycles in highly strongly connected tournaments. ★★

Author(s): Thomassen

Conjecture For every $k\geq 2$ , there is an integer $f(k)$ so that every strongly $f(k)$ -connected tournament has $k$ edge-disjoint Hamilton cycles.

Keywords:

Posted by fhavet
updated March 8th, 2013

add new comment

Graph Theory » Basic G.T.

Subgraph of large average degree and large girth. ★★

Author(s): Thomassen

Conjecture For all positive integers $g$ and $k$ , there exists an integer $d$ such that every graph of average degree at least $d$ contains a subgraph of average degree at least $k$ and girth greater than $g$ .

Keywords:

Posted by fhavet
updated March 5th, 2013

add new comment

Graph Theory » Directed Graphs

Arc-disjoint out-branching and in-branching ★★

Author(s): Thomassen

Conjecture There exists an integer $k$ such that every $k$ -arc-strong digraph $D$ with specified vertices $u$ and $v$ contains an out-branching rooted at $u$ and an in-branching rooted at $v$ which are arc-disjoint.

Keywords:

Posted by fhavet
updated March 2nd, 2013

add new comment

Graph Theory » Coloring » Vertex coloring