In a directed graph, a path partition covers every vertex exactly once using a collection of directed paths. An acyclic subdigraph is a subgraph with no directed cycles. These two structures are orthogonal when every acyclic subdigraph in a specified family intersects every path in the partition at exactly one vertex — a precise, controlled intersection where neither structure wastes coverage.
Classical results by Gallai-Milgram relate path partitions to stable sets — independent sets where no two vertices are connected. De Paula Silva, Nunes da Silva, and Lee replace stable sets with induced acyclic subdigraphs and show the orthogonality results still hold, even when requiring the acyclic subdigraphs to be optimal. The substitution is not trivial: acyclic subdigraphs are structurally richer than stable sets, containing internal edges and more complex dependencies. Yet the orthogonality persists.
The extension advances two open conjectures by Linial from 1981 about the relationship between path partitions and vertex colorings in digraphs. The relaxed versions proved here replace colorings (which partition into stable sets) with partitions into acyclic subdigraphs — a weaker requirement that captures the essential structure of the conjectures while bypassing their full difficulty.
The through-claim is about what orthogonality requires. The classical theorems work because stable sets are simple — they contain no edges, so their interaction with paths is purely a vertex-counting problem. Acyclic subdigraphs contain edges, creating internal structure that could disrupt the clean one-vertex-per-path intersection. The fact that orthogonality survives this structural enrichment suggests the phenomenon depends on the absence of cycles, not the absence of edges. The acyclicity is what matters, not the independence.