Orthogonality between acyclic subdigraphs and paths in digraphs
This work addresses theoretical graph theory problems, providing incremental extensions to classical results and conjectures in digraphs.
The paper tackles the problem of orthogonal relationships between acyclic subdigraphs and paths in digraphs, showing that replacing stable sets with induced acyclic subdigraphs allows analogous statements to hold for optimal path partitions and longest paths, and proves relaxations of two open conjectures by Linial.
Let $D$ be a digraph. A collection of disjoint sets of vertices (respec., collection of disjoint subdigraphs) $\mathcal{H}$ of $D$ and a vertex subset (or subdigraph) $Q$ of $D$ are orthogonal if every set (respec., subdigraph) $H \in \mathcal{H}$ contains exactly one vertex of $Q$. A well-known result of Gallai and Milgram shows that for every minimum path partition of a digraph there is a stable set orthogonal to it. Similarly, Gallai, Hasse, Roy and Vitaver independently proved that for every longest path of a digraph there is a vertex partition into stable sets (i.e, vertex-coloring) orthogonal to it. Berge showed that no analogous statements hold when optimality is required for the stable set or the vertex coloring. In this paper, we show that this holds if we replace stable sets by induced acyclic subdigraphs. In 1981, Linial proposed two generalizations of Gallai-Milgram and Gallai-Hasse-Roy-Vitaver results using a positive integer $k$ as a measure of optimality for the path partition and the coloring, respectively. These generalizations have led to two conjectures that remain open. Using the same strategy of replacing stable sets by induced acyclic subdigraphs, we prove relaxations of both conjectures.