Orthogonality between acyclic subdigraphs and paths in digraphs
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)…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2603.17115
curl -X POST /api/v1/records/arxiv/2603.17115/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2603.17115/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'