pith. sign in

arxiv: 2603.17115 · v2 · submitted 2026-03-17 · 🧮 math.CO · cs.DM

Orthogonality between acyclic subdigraphs and paths in digraphs

Caroline A. de Paula Silva , C\^andida Nunes da Silva , Orlando Lee This is my paper

Pith reviewed 2026-05-15 09:29 UTC · model grok-4.3

classification 🧮 math.CO cs.DM MSC 05C20
keywords digraphspath partitionsinduced acyclic subdigraphsorthogonalityGallai-Milgram theoremLinial conjectureslongest pathsacyclic induced subgraphs
0
0 comments X

The pith

Replacing stable sets with induced acyclic subdigraphs restores orthogonality for minimum path partitions and longest paths in digraphs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

In any digraph, every minimum path partition admits an induced acyclic subdigraph orthogonal to it, so that each path contains exactly one vertex from the subdigraph. Likewise, every longest path admits an orthogonal partition of the vertices into induced acyclic subdigraphs. These statements hold in place of the classical Gallai-Milgram and Gallai-Hasse-Roy-Vitaver theorems once stable sets are replaced by induced acyclic subdigraphs; the replacement also yields relaxations of Linial's two open conjectures that parameterize the optimality of the partitions and colorings. A reader would care because the new objects give guaranteed intersection properties where stable-set versions fail under simultaneous optimality requirements.

Core claim

The paper shows that for every minimum path partition there is an induced acyclic subdigraph orthogonal to it, and for every longest path there is a partition into induced acyclic subdigraphs orthogonal to it. It also proves relaxations of Linial's conjectures by applying the same replacement of stable sets with induced acyclic subdigraphs.

What carries the argument

Orthogonality between a collection of disjoint induced acyclic subdigraphs and a path partition (or single path), defined so each subdigraph contains exactly one vertex from the partition (or path).

If this is right

  • Every minimum path partition admits an orthogonal induced acyclic subdigraph.
  • Every longest path admits an orthogonal partition into induced acyclic subdigraphs.
  • Relaxed versions of both of Linial's conjectures hold when stable sets are replaced by induced acyclic subdigraphs.
  • The orthogonality properties supply new min-max relations between path partitions and acyclic induced substructures.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The substitution technique may apply to other hereditary classes of subdigraphs beyond induced acyclicity.
  • Such orthogonality could yield new bounds on the directed feedback vertex set number in relation to path partitions.
  • The relaxations might be tightened by imposing mild degree or connectivity conditions on the digraph.
  • The results suggest examining whether similar replacements work for other classical theorems that use stable sets in digraphs.
  • msc

Load-bearing premise

The combinatorial arguments used to replace stable sets with induced acyclic subdigraphs extend without additional restrictions to the minimum path partitions and to the k-parameterized versions in Linial's conjectures.

What would settle it

A concrete digraph whose minimum path partition has no induced acyclic subdigraph that meets each path in exactly one vertex.

Figures

Figures reproduced from arXiv: 2603.17115 by C\^andida Nunes da Silva, Caroline A. de Paula Silva, Orlando Lee.

Figure 1
Figure 1. Figure 1: Orientation D of a C5 that is a counterexample to both Question 1 and Ques￾tion 2. 2 [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper extends the Gallai-Milgram theorem by showing that every minimum path partition of a digraph admits an orthogonal induced acyclic subdigraph, and extends the Gallai-Hasse-Roy-Vitaver theorem by showing that every longest path admits an orthogonal partition into induced acyclic subdigraphs. It further establishes relaxations of Linial's two k-parameterized conjectures by applying the same replacement of stable sets with induced acyclic subdigraphs.

Significance. If the combinatorial arguments hold, the results supply a uniform relaxation that restores orthogonality in cases where it fails for stable sets, yielding new structural information on path partitions and longest paths in digraphs. The partial progress on Linial's open conjectures is a concrete contribution that may inform future work on parameterized versions.

minor comments (3)
  1. The abstract states that the combinatorial arguments 'carry over' but does not indicate whether any additional case analysis is required when acyclicity is required to be induced rather than merely transitive; a short clarifying sentence would strengthen the claim.
  2. Notation for orthogonality is introduced for both sets and subdigraphs; ensure the two definitions are displayed side-by-side in the preliminaries section to avoid any ambiguity for readers.
  3. The relaxations of Linial's conjectures are described only at a high level; stating the precise k-parameterized statements that are proved (e.g., which bound is relaxed) would make the contribution easier to compare with the original conjectures.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript and the recommendation of minor revision. We address the referee's summary of our results below.

read point-by-point responses

  1. Referee: The paper extends the Gallai-Milgram theorem by showing that every minimum path partition of a digraph admits an orthogonal induced acyclic subdigraph, and extends the Gallai-Hasse-Roy-Vitaver theorem by showing that every longest path admits an orthogonal partition into induced acyclic subdigraphs. It further establishes relaxations of Linial's two k-parameterized conjectures by applying the same replacement of stable sets with induced acyclic subdigraphs.

    Authors: We thank the referee for this accurate summary. Our proofs indeed establish the stated orthogonality results by replacing stable sets with induced acyclic subdigraphs, and the relaxations of Linial's conjectures follow directly from the same substitution. We are pleased that the uniform relaxation and its implications for path partitions and longest paths are viewed as a concrete contribution. revision: no

Circularity Check

0 steps flagged

No significant circularity; direct combinatorial proofs extending known theorems

full rationale

The paper establishes orthogonality results by replacing stable sets with induced acyclic subdigraphs in the Gallai-Milgram theorem (minimum path partitions) and the Gallai-Hasse-Roy-Vitaver theorem (longest paths), then applies the identical replacement to obtain relaxations of Linial's two k-parameterized conjectures. These are presented as existence proofs via combinatorial arguments that carry over without additional restrictions or fitted quantities. No equations define quantities in terms of themselves or prior self-citations, no parameters are optimized against subsets of data, and no uniqueness theorems or ansatzes are imported from the authors' own prior work to force the result. The derivation chain consists of direct extensions of externally known theorems and remains self-contained against combinatorial benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies only on standard facts about digraphs, path partitions, and induced subdigraphs; no new numerical parameters are fitted, no ad-hoc axioms are introduced, and no new entities are postulated.

axioms (1)
  • standard math Standard properties of finite digraphs, path partitions, and induced subdigraphs
    The proofs build directly on the cited Gallai-Milgram and Gallai-Hasse-Roy-Vitaver theorems without additional assumptions.

pith-pipeline@v0.9.0 · 5566 in / 1222 out tokens · 39839 ms · 2026-05-15T09:29:14.390921+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

30 extracted references · 30 canonical work pages

  1. [1]

    Aboulker, P

    P. Aboulker, P. Charbit, and R. Naserasr. Extension of Gy´ arf´ as-Sumner conjecture to digraphs.The Electronic Journal of Combinatorics, 2021

    work page 2021

  2. [2]

    Aubian.Colouring digraphs

    G. Aubian.Colouring digraphs. PhD thesis, Universit´ e Paris Cit´ e, 2023

    work page 2023

  3. [3]

    Bang Jensen and G

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

    work page 2008

  4. [4]

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

    work page 1982

  5. [5]

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

    work page 1982

  6. [6]

    Bokal, G

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

    work page 2004

  7. [7]

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

    work page 2008

  8. [8]

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

    work page 2023

  9. [9]

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

    work page 2024

  10. [10]

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

    work page 2025

  11. [11]

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

    work page 2022

  12. [12]

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

    work page 2022

  13. [13]

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

    work page 2023

  14. [14]

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

    work page 2022

  15. [15]

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

    work page 2022

  16. [16]

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

    work page 2054

  17. [17]

    Gallai and A

    T. Gallai and A. N. Milgram. Verallgemeinerung eines graphentheoretischen Satzes von R´ edei.Acta Sci Math, 21:181–186, 1960

    work page 1960

  18. [18]

    P. Hall. On representatives of subsets. InClassic Papers in Combinatorics, pages 58–62. Springer, 1987

    work page 1987

  19. [19]

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

    work page 2006

  20. [20]

    M. Hasse. Zur algebraischen begr¨ undung der graphentheorie. i.Mathematische Nachrichten, 28(5-6):275–290, 1965

    work page 1965

  21. [21]

    Kawarabayashi and L

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

    work page 2025

  22. [22]

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

    work page 1981

  23. [23]

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

    work page 2003

  24. [24]

    Neumann-Lara

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

    work page 1982

  25. [25]

    Picasarri-Arrieta.Digraph colouring

    L. Picasarri-Arrieta.Digraph colouring. PhD thesis, Universit´ e Cˆ ote d’Azur, 2024

    work page 2024

  26. [26]

    Picasarri-Arrieta

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

    work page 2024

  27. [27]

    B. Roy. Nombre chromatique et plus longs chemins d’un graphe.Revue fran¸ caise d’informatique et de recherche op´ erationnelle, 1(5):129–132, 1967

    work page 1967

  28. [28]

    Sambinelli.Partition problems in graphs and digraphs

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

    work page 2018

  29. [29]

    Sambinelli, C

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

    work page 2022

  30. [30]

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

    work page 1962