Longest paths in strong spanning oriented subgraphs of strong semicomplete multipartite digraphs (Q1579571)

A digraph obtained by replacing each edge of a complete multipartite graph by an arc or a pair of mutually opposite arcs is called a semicomplete digraph. An oriented graph is a digraph with no directed cycle of length two. In [Ars Comb. 58, 271-278 (2001)], the reviewer raised the following question: Let \(D\) be a strong semicomplete multipartite digraph with a longest directed path of length \(p\). Does there exist a strong spanning oriented subgraph with a longest directed path of length \(p\)? The authors present the following complete answer to this question. Every strong semicomplete multipartite digraph \(D\) with a longest directed path of length \(p\), which is not bipartite with a partite set of cardinality one, has a strong spanning oriented subgraph with a longest directed path of length at least \(p-2\). Examples show that the bound \(p-2\) is best possible.