Tournaments


Monochromatic reachability or rainbow triangles ★★★

Author(s): Sands; Sauer; Woodrow

In an edge-colored digraph, we say that a subgraph is \emph{rainbow} if all its edges have distinct colors, and \emph{monochromatic} if all its edges have the same color.

\begin{problem} Let $G$ be a tournament with edges colored from a set of three colors. Is it true that $G$ must have either a rainbow directed cycle of length three or a vertex $v$ so that every other vertex can be reached from $v$ by a monochromatic (directed) path? \end{problem}

Keywords: digraph; edge-coloring; tournament

Decomposing an even tournament in directed paths. ★★★

Author(s): Alspach; Mason; Pullman

\begin{conjecture} Every tournament $D$ on an even number of vertices can be decomposed into $\sum_{v\in V}\max\{0,d^+(v)-d^-(v)\}$ directed paths. \end{conjecture}

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:

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:

Decomposing k-arc-strong tournament into k spanning strong digraphs ★★

Author(s): Bang-Jensen; Yeo

\begin{conjecture} Every k-arc-strong tournament decomposes into k spanning strong digraphs. \end{conjecture}

Keywords:


Syndicate content