Orthogonality between acyclic subdigraphs and paths in digraphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916000619823104 |
|---|---|
| author | Silva, Caroline A. de Paula da Silva, Cândida Nunes Lee, Orlando |
| author_facet | Silva, Caroline A. de Paula da Silva, Cândida Nunes Lee, Orlando |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_17115 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Orthogonality between acyclic subdigraphs and paths in digraphs Silva, Caroline A. de Paula da Silva, Cândida Nunes Lee, Orlando Combinatorics Discrete Mathematics 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. |
| title | Orthogonality between acyclic subdigraphs and paths in digraphs |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2603.17115 |