{"id":"01917894-29bd-41d8-94f5-756a5a78c861","arxiv_id":"2507.10266","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"For every large enough Δ, a digraph with bounded geometric-mean degree or bounded out-degree and no large biclique or special directed obstruction is dicolourable with Δ−1 colours.","lead":"This paper proves digraph analogues of the Borodin-Kostochka conjecture for all sufficiently large maximum degrees, with a single directed obstruction. It also introduces a dense decomposition lemma for digraphs that is likely to be useful beyond colouring.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The main Theorems 8 and 12 are long but internally coherent; the weakest load-bearing point is the unproved Proposition 7.3 from the authors' preprint [25], which is the sole support for the third generalization (Corollaries 13, 14, and 30).","rationale":"Good-faith reading: the abstract and introduction promise three independent generalisations of Reed's theorem. Theorems 8 and 12 are the first two and are supported by a substantial, largely self-contained proof: Lemma 9 is proved in full, and Section 4's probabilistic machinery is detailed enough that I could trace the main estimates. The third generalisation, however, is not self-contained: Corollary 30 explicitly outsources its key step to Proposition 7.3 of [25], a preprint by two of the four authors, without proof. The reader's weakest_assumption identifies exactly this dependency, and my independent read agrees. I did not find a competing flaw in Theorem 8 or 12: the dense-decomposition lemma's claims (Claims 9.1–9.7) check out; the quasi-biclique structure (Lemma 24), the saviour lemmas (Lemmas 25–27), and the Lovász Local Lemma application (Lemma 29) are internally consistent, with all constants reconcilable for large Δ. The proof of Theorem 12 uses Theorem 8 only in the balanced case (Claim 12.2) and otherwise constructs an extension argument; the discharging step (Claim 12.5) is valid given the lower bounds d± ≥ Δ−1. Therefore the main theorems are not in jeopardy from the external dependency. But because Corollaries 13, 14, and 30 are advertised results and rest entirely on an unverified external proposition, the conditional verdict is appropriate. The concern can be settled by either supplying a proof of Proposition 7.3 or by a computational falsification attempt; absence of a counterexample on small digraphs would reduce but not eliminate the risk, since no finite search can verify a universal statement.","tokens_in":49472,"tokens_out":23391,"duration_ms":252009,"concrete_test":"Independently re-derive [25, Proposition 7.3] from the definitions in Corollary 30: prove that every (∆min(D))-dicolouring of D̂ pulls back to a (∆min(D))-dicolouring of D, establishing χ̂(D̂) ≥ χ̂(D). In parallel, run an exhaustive search over all digraphs on n ≤ 6 vertices: for each D compute χ̂(D), ∆min(D), build D̂, and test whether ∆+(D̂) ≤ ∆min(D) and χ̂(D̂) ≥ χ̂(D). A single violation would falsify the proposition and invalidate Corollaries 13, 14, and 30; if no violation is found, the proposition still requires a full proof, but the risk is localized to the missing argument.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I found no internal inconsistency in the proofs of Theorems 8 and 12: the dense decomposition lemma (Lemma 9) is proved from first principles, and the probabilistic argument in Section 4.2 (Lemma 29) has plausible estimates with the stated Talagrand and Azuma bounds. The load-bearing weakness is in Section 6. Corollary 30 is derived from Theorem 12 by a two-step transformation (remove arcs from B to A, digonify arcs from A to B, then reverse arcs inside D[B]). The proof of Corollary 30 contains the sentence: 'It was proved in [25, Proposition 7.3] that ∆+(D̂) ≤ ∆min(D) ≤ ∆ and χ̂(D̂) ≥ χ̂(D) ≥ ∆, we omit the proof.' This proposition is not proved in the present paper, is not machine-checked, and is taken from an unreviewed same-author preprint. If the inequality χ̂(D̂) ≥ χ̂(D) fails, then Theorem 12 cannot be applied to D̂, and Corollary 30, together with its consequences Corollaries 13 and 14 and the advertised 'third independent generalisation of Reed's result', collapses. Theorems 8 and 12 themselves do not depend on this proposition and remain plausible. The thresholds are existential and the proofs are long, but that is not by itself a defect.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes three digraph analogues of the Borodin–Kostochka and Reed theorems, replacing maximum degree, clique number, and chromatic number by geometric-mean degree, biclique number, and dichromatic number. The main theorems, Theorem 8 for the geometric-mean degree and Theorem 12 for the maximum out-degree, assert that for large Δ every digraph with the relevant degree parameter at most Δ and biclique number at most Δ−1 is (Δ−1)-dicolourable unless it contains the unique obstruction C3 ⊞ K_{Δ−2}. The proofs introduce a directed dense decomposition lemma (Lemma 9) and combine structural analysis with the Lovász Local Lemma, Talagrand's inequality, and Azuma's inequality. Section 6 derives Corollaries 13 and 14, giving a third generalisation via Δmin, and proves an NP-completeness result (Proposition 15). Theorems 8 and 12 appear to be proved from first principles, but the derivation of Corollary 30, and hence of Corollaries 13 and 14, relies on an unproved proposition from the authors' preprint [25].","tokens_in":49773,"tokens_out":8763,"duration_ms":98257,"significance":"If Theorems 8 and 12 are correct, they are substantial and natural generalizations of Reed's theorem to digraphs, with a clean directed obstruction, and the dense decomposition lemma is likely to be a useful tool in further work on digraph colouring. The proofs are detailed, internally coherent, and do not rely on fitted parameters: the thresholds are existential and all probability estimates are justified. However, the advertised third independent generalization, based on Corollary 30, is not established within the manuscript because its key step is delegated to an unreviewed same-author preprint. The paper would be acceptable for publication after this gap is addressed.","major_comments":[{"comment":"","section":"6"}],"minor_comments":[{"comment":"The phrase 'Adigon is a pair of arcs...' contains a typo; it should read 'A digon is a pair of arcs...'.","section":"2.1"},{"comment":"The first sentence of the proof of Claim 12.15 says 'Assume for a contradiction that |I≤6| ≥ 43', but the claim being proved bounds |I>6|; the subscript should be >6.","section":"5, Claim 12.15"},{"comment":"In the definition of W_{x,y}, the expression 'N^+(s) ∪ N(x) ∪ N(y) \\ {x,y}' is clearer with parentheses around the union before the set difference.","section":"4.2, Claim 29.1"},{"comment":"The remark that every k-obstruction contains a biclique of size ⌈(k−1)/2⌉ is true, but a one-line justification would help, since the biclique may need to be taken inside one side of the partition (A,B) rather than across it.","section":"6"}],"recommendation":"major_revision","confidential_remarks":"The main results, Theorems 8 and 12, are strong and appear to be proved carefully. The only serious obstacle is the external dependence of Section 6 on [25, Proposition 7.3]. I would be willing to support acceptance once that proposition is proved in the manuscript or the corollaries are explicitly made conditional on it; the latter would require adjusting the abstract and introduction."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This paper is worth your time. It proves directed analogues of Reed's large-Δ Borodin–Kostochka theorem under two degree measures, geometric-mean degree and maximum out-degree, and introduces a new directed obstruction (C3 ⊞ K_{Δ−2}) that is genuinely novel. Theorem 8 and Theorem 12 are the main results, and the dense decomposition lemma (Lemma 9) generalizing Molloy–Reed looks like a useful tool beyond this paper. I read the core proofs of Theorems 8 and 12 fairly carefully, and they are internally coherent: the structural claims check out, the probabilistic estimates are plausible, and there are no fitted parameters or circular steps in the main argument. The existential thresholds (Δ8, Δ12) are not explicit, but that is normal for this kind of proof and not a defect.\n\nThe real soft spot is Section 6. Corollary 30, and with it Corollaries 13 and 14, rest on Proposition 7.3 of the authors' own preprint [25], which is stated without proof here, is not machine-checked, and is from an unreviewed source. To the authors' credit, they flag this explicitly ('we omit the proof'), but it remains a load-bearing dependency for the so-called third independent generalization. If that proposition fails, those corollaries collapse. Theorems 8 and 12 do not depend on it, so the paper's core contribution stands regardless. I also note that the proof of Theorem 12 uses a discharging argument with a case distinction that is long but seems sound; the boundedness claims for I±, I≤6, I>6 are the kind of technical steps where small errors hide, but I did not find one.\n\nWho should read this? Anyone working on digraph colouring, Reed-type results, or the probabilistic method for digraphs. I would cite Theorems 8 and 12 in my own work if I needed a directed Reed-type bound. I would also bring it to a reading group—there is enough meat in the dense decomposition lemma and the obstruction to spark discussion.\n\nRecommendation: send it to peer review. A serious referee should be asked to verify Proposition 7.3 or to require that it be proved in the paper, but the main theorems deserve refereeing on their own. Conditional acceptance after that dependency is cleaned up would be a reasonable outcome.","headline":"A substantial large-Δ directed analogue of Reed's theorem with a genuinely new obstruction, but the third generalization leans on an unproved external proposition.","tokens_in":50366,"tokens_out":1213,"would_cite":true,"duration_ms":14977,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C20","05C15"],"pacs":[],"model":"deepseek-v4-flash","headline":"Large digraphs with no large biclique are (Δ−1)-dicolourable unless one obstruction appears","keywords":["dichromatic number","biclique number","Borodin–Kostochka conjecture","Reed's conjecture","dense decomposition","digraph colouring","maximum out-degree","directed Brooks theorem"],"falsifier":"Find, for arbitrarily large Δ, a digraph with $\\tilde{\\Delta}(D)\\le\\Delta$ and $\\overleftrightarrow{\\omega}(D)\\le\\Delta-1$ that contains no $\\vec{C}_3\\boxtimes\\overleftrightarrow{K}_{\\Delta-2}$ and still has dichromatic number at least Δ; such a digraph would disprove Theorem 8. Alternatively, exhibit a digraph for which the transformation promised by Proposition 7.3 of [25] increases the dichromatic number, which would refute Corollaries 13 and 14.","tokens_in":49273,"feed_emoji":"🎨","tokens_out":8958,"duration_ms":97531,"temperature":0.7,"pith_summary":"The paper proves, for all sufficiently large integers Δ, a directed analogue of the Borodin–Kostochka conjecture. The claim is that a digraph whose largest geometric-mean degree $\\tilde{\\Delta}$ is at most Δ and whose biclique number is at most Δ−1 has dichromatic number at most Δ−1, with exactly one exception: a directed 3-cycle completely joined to a complete digraph on Δ−2 vertices. The same conclusion holds when the bound is imposed only on the out-degree $\\Delta^+$ rather than on $\\tilde{\\Delta}$. From these results the paper derives sufficient conditions phrased through $\\Delta_{\\min}$, the smaller of the in- and out-degree, and shows that one of these conditions is best possible through an NP-completeness result. The proof introduces a dense decomposition lemma for digraphs that transfers the classical dense-decomposition technique for graphs into the directed setting.","feed_headline":"Large digraphs colour with Δ−1 colours unless one obstruction appears","feed_subtitle":"Bounded degree and no large biclique force an acyclic (Δ−1)-colouring.","key_machinery":"The load-bearing tool is the Dense Decomposition Lemma: for $0<\\varepsilon<1/2$ and a sublinear function $d$, every sufficiently large digraph admits a partition $X_1\\sqcup\\cdots\\sqcup X_t\\sqcup S$ where each $X_i$ has size about $\\Delta_{\\max}$, bounded arc boundary, and consists exactly of vertices with almost $\\Delta_{\\max}$ out-neighbours inside $X_i$, while vertices in $S$ are $d$-sparse. This lets the authors isolate quasi-biclique clusters, prove structural lemmas about special vertices they call saviours, and then run a Lovász Local Lemma-based random uncolouring argument: sparse vertices see repeated colours, and dense clusters are handled cluster by cluster. The unique obstruction $\\vec{C}_3\\boxtimes\\overleftrightarrow{K}_{\\Delta-2}$ is exactly the configuration on which this strategy is forced to fail.","core_discovery":"What the paper establishes is a dichotomy, not just a bound: for every large Δ, the only way a digraph with $\\tilde{\\Delta}(D)\\le\\Delta$ and $\\overleftrightarrow{\\omega}(D)\\le\\Delta-1$ can need Δ colours is the explicit block $\\vec{C}_3\\boxtimes\\overleftrightarrow{K}_{\\Delta-2}$. It proves the same dichotomy when $\\Delta^+(D)$ replaces $\\tilde{\\Delta}(D)$, and then converts the out-degree statement into a $\\Delta_{\\min}$-based sufficient condition: if the biclique number is smaller than $(\\Delta-1)/2$, or the underlying graph has clique number at most $\\Delta-1$, then $\\Delta_{\\min}(D)\\le\\Delta$ forces a $(\\Delta-1)$-dicolouring. On symmetric digraphs the first dichotomy specialises to the undirected Borodin–Kostochka theorem for large Δ.","pith_inferences":["The dense decomposition lemma is likely to be reusable: future proofs that bound a digraph parameter by splitting into sparse vertices and near-biclique clusters could run through the same partition.","If Proposition 7.3 of the cited preprint is supplied with a full proof, the $\\Delta_{\\min}$ corollaries become completely self-contained; as it stands their unconditional status depends on that external result.","The global dichotomy suggests a practical recognition angle: for large Δ, a digraph violating the bound must contain a small certificate of size Δ−1, so the bad case is structurally compressible rather than scattered."],"forward_implications":["If Theorem 8 is correct, every symmetric digraph obtained from a graph with maximum degree Δ and clique number at most Δ−1 is (Δ−1)-dicolourable, reproducing the undirected Borodin–Kostochka result for large Δ.","The obstruction is unique: the only directed phenomenon preventing such a colouring is a directed triangle fused through every possible two-way arc to a complete digraph on Δ−2 vertices.","Corollary 14 gives a new route to the undirected theorem: a digraph whose underlying graph has clique number at most Δ−1 and whose smaller-degree parameter is at most Δ is (Δ−1)-dicolourable.","The NP-completeness result shows that the biclique-size threshold in Corollary 13 cannot be improved without changing the complexity of the decision problem.","The dense decomposition lemma alone provides a reusable decomposition for large-degree digraphs, independent of the colouring application."],"supporting_citations":[{"why":"proves the undirected Borodin–Kostochka statement for large maximum degree, the result being generalised.","marker":"[39]"},{"why":"introduces the convex-combination colouring bound and the dense-decomposition and random-colouring framework that the paper adapts.","marker":"[38]"},{"why":"poses the digraph Reed conjecture and supplies the convex-combination theorem used as a starting point.","marker":"[26]"},{"why":"gives the directed Brooks theorem that controls critical digraphs and the structure of obstructions.","marker":"[30]"},{"why":"provides Proposition 7.3, the unproved transformation on which Corollaries 13 and 14 depend.","marker":"[25]"},{"why":"is the source of the dense-decomposition technique for colouring graphs with almost the maximum number of colours.","marker":"[34]"}],"fun_headline_variants":["Large digraphs colour with Δ−1 unless a rare block appears","Dichotomy: Δ−1 dicolouring or a specific obstruction in digraphs","No big biclique means large digraphs colour with Δ−1","Borodin–Kostochka generalized to digraphs for large Δ","Dense decomposition lemma helps dicolour large digraphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The two large-degree theorems are built on the dense decomposition lemma, but the $\\Delta_{\\min}$ corollaries additionally rely on Proposition 7.3 from the cited preprint [25], an unproved transformation that is stated to preserve the dichromatic number while bounding the out-degree, and that the present paper quotes without proof.","fun_headline_variants_meta":{"raw":{"variants":["Large digraphs colour with Δ−1 unless a rare block appears","Dichotomy: Δ−1 dicolouring or a specific obstruction in digraphs","No big biclique means large digraphs colour with Δ−1","Borodin–Kostochka generalized to digraphs for large Δ","Dense decomposition lemma helps dicolour large digraphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000682,"raw_usage":{"total_tokens":3198,"prompt_tokens":1147,"completion_tokens":2051,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":763,"completion_tokens_details":{"reasoning_tokens":1951}},"tokens_in":763,"tokens_out":2051,"duration_ms":20208,"temperature":1.0,"reasoning_tokens":1951,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T17:36:45.660541+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find, for arbitrarily large Δ, a digraph with $\\tilde{\\Delta}(D)\\le\\Delta$ and $\\overleftrightarrow{\\omega}(D)\\le\\Delta-1$ that contains no $\\vec{C}_3\\boxtimes\\overleftrightarrow{K}_{\\Delta-2}$ and still has dichromatic number at least Δ; such a digraph would disprove Theorem 8. Alternatively, exhibit a digraph for which the transformation promised by Proposition 7.3 of [25] increases the dichromatic number, which would refute Corollaries 13 and 14.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"introduces the convex-combination colouring bound and the dense-decomposition and random-colouring framework that the paper adapts."},{"cited_title":"Kawarabayashi and L","cited_arxiv_id":null,"evidence_quote":"poses the digraph Reed conjecture and supplies the convex-combination theorem used as a starting point."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"gives the directed Brooks theorem that controls critical digraphs and the structure of obstructions."}],"review_version":1}