Orthogonality between acyclic subdigraphs and paths in digraphs

• Caroline A. de Paula Silva UNICAMP
• Cândida Nunes da Silva UFSCar
• Orlando Lee UNICAMP

DOI: https://doi.org/10.5753/etc.2026.21043

Resumo

Let D be a digraph. A collection of disjoint sets of vertices (respec., collection of disjoint subdigraphs) H of D and a vertex subset (or subdigraph) Q of D are orthogonal if every set (respec., subdigraph) H ∈ 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.

Referências

Aboulker, P., Charbit, P., and Naserasr, R. (2021). Extension of Gyárfás-Sumner conjecture to digraphs. The Electronic Journal of Combinatorics.

Aubian, G. (2023). Colouring digraphs. PhD thesis, Université Paris Cité.

Bang Jensen, J. and Gutin, G. Z. (2008). Digraphs: theory, algorithms and applications. Springer Science & Business Media.

Berge, C. (1982a). Diperfect graphs. Combinatorica, 2(3):213–222.

Berge, C. (1982b). k-optimal partitions of a directed graph. European Journal of Combinatorics, 3(2):97–101.

Bokal, D., Fijavz, G., Juvan, M., Kayll, P. M., and Mohar, B. (2004). The circular chromatic number of a digraph. Journal of Graph Theory, 46(3):227–240.

Bondy, J. A. and Murty, U. S. R. (2008). Graph Theory. Springer.

de Paula Silva, C. A., da Silva, C. N., and Lee, O. (2023). Obstructions for χ-diperfectness. In Procedia Computer Science. LAGOS 2023: XII Latin-American Algorithms, Graphs and Optimization Symposium. To appear.

de Paula Silva, C. A., da Silva, C. N., and Lee, O. (2024). BE-Diperfect Digraphs with Stability Number Two. The Electronic Journal of Combinatorics, pages P2–43.

de Paula Silva, C. A., da Silva, C. N., and Lee, O. (2025). Acyclic α-diperfect digraphs with stability number two. Procedia Computer Science, 273:110–116.

de Paula Silva, C. A., Nunes da Silva, C., and Lee, O. (2022a). χ-Diperfect digraphs. Discrete Mathematics, 345(9):112941.

de Paula Silva, C. A., Nunes da Silva, C., and Lee, O. (2022b). On χ-Diperfect Digraphs with Stability Number Two. In Castañeda, A. and Rodríguez-Henríquez, F., editors, LATIN 2022: Theoretical Informatics, pages 460–475, Cham. Springer International Publishing.

de Paula Silva, C. A., Nunes da Silva, C., and Lee, O. (2023). A family of counterex-amples for a conjecture of Berge on α-diperfect digraphs. Discrete Mathematics, 346(8):113458.

de Paula Silva, C. A., Nunes da Silva, C., and Lee, O. (2026). Orthogonality between acyclic subdigraphs and paths in digraphs. arXiv preprint arXiv:2603.17115. arXiv: 2603.17115.

Freitas, L. I. B. and Lee, O. (2022a). 3-anti-circulant digraphs are α-diperfect and BE-diperfect. Open Journal of Discrete Mathematics.

Freitas, L. I. B. and Lee, O. (2022b). Some Results on Berge’s Conjecture and Begin–End Conjecture. Graphs and Combinatorics, 38(4):1–23.

Gallai, T. (1968). On directed paths and circuits. Theory of graphs, 38:2054.

Gallai, T. and Milgram, A. N. (1960). Verallgemeinerung eines graphentheoretischen Satzes von Rédei. Acta Sci Math, 21:181–186.

Hall, P. (1987). On representatives of subsets. In Classic Papers in Combinatorics, pages 58–62. Springer.

Hartman, I. B.-A. (2006). Berge’s conjecture on directed path partitions—a survey. Discrete mathematics, 306(19-20):2498–2514.

Hasse, M. (1965). Zur algebraischen Btegründung der Graphentheorie. i. Mathematische Nachrichten, 28(5-6):275–290.

Kawarabayashi, K.-i. and Picasarri-Arrieta, L. (2025). An analogue of Reed’s conjecture for digraphs. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3310–3324. SIAM.

Linial, N. (1981). Extending the Greene-Kleitman theorem to directed graphs. Journal of Combinatorial Theory, Series A, 30(3):331–334.

Mohar, B. (2003). Circular colorings of edge-weighted graphs. Journal of Graph Theory, 43(2):107–116.

Neumann-Lara, V. (1982). The dichromatic number of a digraph. Journal of Combinatorial Theory, Series B, 33(3):265–270.

Picasarri-Arrieta, L. (2024a). Digraph colouring. PhD thesis, Université Côte d’Azur.

Picasarri-Arrieta, L. (2024b). Strengthening the Directed Brooks’ Theorem for oriented graphs and consequences on digraph redicolouring. Journal of Graph Theory, 106(1):5–22.

Roy, B. (1967). Nombre chromatique et plus longs chemins d’un graphe. Revue française d’informatique et de recherche opérationnelle, 1(5):129–132.

Sambinelli, M. (2018). Partition problems in graphs and digraphs. PhD thesis, State University of Campinas - UNICAMP.

Sambinelli, M., da Silva, C. N., and Lee, O. (2022). α-Diperfect digraphs. Discrete Mathematics, 345(5):112759.

Vitaver, L. (1962). Determination of minimal coloring of vertices of a graph by means of boolean powers of the incidence matrix. In Doklady Akademii Nauk, volume 147, pages 758–759. Russian Academy of Sciences.