Thomassen, Carsten


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

Author(s): Thomassen

\begin{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$. \end{problem}

Keywords:

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

Author(s): Thomassen

\begin{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. \end{conjecture}

Keywords:

Subgraph of large average degree and large girth. ★★

Author(s): Thomassen

\begin{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$. \end{conjecture}

Keywords:

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

Author(s): Thomassen

\begin{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.

% Enter your conjecture in LaTeX % You may change "conjecture" to "question" or "problem" if you prefer. \end{conjecture}

Keywords:

Counting 3-colorings of the hex lattice ★★

Author(s): Thomassen

\begin{problem} Find $\lim_{n \rightarrow \infty} (\chi( H_n , 3)) ^{ 1 / |V(H_n)| }$. \end{problem}

Keywords: coloring; Lieb's Ice Constant; tiling; torus

Chords of longest cycles ★★★

Author(s): Thomassen

\begin{conjecture} If $G$ is a 3-connected graph, every longest cycle in $G$ has a chord. \end{conjecture}

Keywords: chord; connectivity; cycle

The Bermond-Thomassen Conjecture ★★

Author(s): Bermond; Thomassen

\begin{conjecture} For every positive integer $k$, every digraph with minimum out-degree at least $2k-1$ contains $k$ disjoint cycles. \end{conjecture}

Keywords: cycles

Hamiltonian cycles in line graphs ★★★

Author(s): Thomassen

\begin{conjecture} Every 4-connected \Def{line graph} is \Def[hamiltonian]{Hamilton cycle}. \end{conjecture}

Keywords: hamiltonian; line graphs

Syndicate content