8 problems

A digraph is semicomplete if it has no pair of non-adjacent vertices. A tournament is an orientation of a complete graph, hence a semicomplete digraph with no directed 2-cycles. A…

Bang-Jensen–DeVos–Mütze conjecture. Every $(2k-1)$-strong semicomplete digraph on at least $2k+1$ vertices contains a spanning $k$-strong tournament.

Let $S$ be a semicomplete digraph, meaning that for every pair of distinct vertices $u,v\in V(S)$, at least one of $uv$ and $vu$ is an arc of $S$. Write…

Let $D$ be a semicomplete digraph, and let $x,y$ be distinct vertices of $D$. A longest $(x,y)$-path is an $(x,y)$-path containing the maximum possible number of arcs. Longest path…

Arc-avoidance conjecture. The digraph $D\setminus A'$ is supereulerian.

Fixed-arc deletion algorithm conjecture. For each fixed positive integer $k$, there exists a polynomial-time algorithm which, given a semicomplete digraph $D=(V,A)$ and…

Spanning eulerian subdigraph avoidance conjecture. Every $(k+1)$-arc-strong semicomplete digraph $D$ has a spanning eulerian subdigraph that avoids any prescribed set of $k$ arcs.

Bang-Jensen and Yeo's conjecture. For every $\lambda\ge 2$ there is a finite set ${\cal S}_{\lambda}$ of digraphs such that every $\lambda$-arc-strong semicomplete digraph $D$ cont…