6 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 $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.