Id: arxiv/2603.17115 Url: https://arxiv.org/abs/2603.17115 Tags: math.CO, cs.DM Score: 0 Title: Orthogonality between acyclic subdigraphs and paths in digraphs Domain: math.CO Source: arxiv Authors: Caroline A. de Paula Silva, Cândida Nunes da Silva, Orlando Lee Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-03-17 Page: https://delphi.science/r/arxiv/2603.17115 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)…