{"id":"65940920-1a01-46ad-ab54-ff10ef0785f4","arxiv_id":"2607.06928","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":3,"one_line_summary":"Every digraph with sufficiently large maximum geometric-mean degree either contains a biclique exceeding that bound minus 2b or has dichromatic number at most that bound minus b.","lead":"The paper proves that digraphs with large maximum geometric-mean degree either contain a large biclique or can be colored with few colors, extending Reed's classical graph coloring theorem to directed graphs. A generalist might read it to understand how coloring constraints generalize when edges have direction.","discovery_kind":"unclear","skeptic_critique":{"model":"glm-5.2","headline":"Vertex identification step (§4.4) relies on Claim 26's common-neighborhood bound, which is the tightest link in the chain; if it degrades, D⋆ degree bounds fail and the LLL application breaks.","rationale":"The reader's weakest_assumption focuses on the Dense Decomposition Lemma (Lemma 13 from [16]). While that is a genuine dependency, the lemma is a structural tool whose statement is clearly specified and whose proof (though from overlapping authors) follows established dense decomposition methodology. The more load-bearing concern for THIS paper's specific argument is the informal distance-preservation argument in §4.5.3, which is the linchpin for the LLL application. The proof is otherwise remarkably detailed — every inequality is traced to specific claims, the probabilistic analysis uses standard tools (Talagrand, Azuma, LLL) correctly, and the vertex identification technique is well-motivated. The tightness construction is clean and verifiable. The threshold Δ_b ≥ 2^{Ω(b²)} is acknowledged as non-optimal but sufficient. My concern about distance preservation is a real but likely-resolvable issue: the common-neighbor property probably does give the factor-3 bound, but it deserves formal verification rather than a one-sentence justification. This does not rise to the level of changing the verdict from CONDITIONAL — the reader's assessment of moderate confidence and conditional acceptance is appropriate. The paper represents a genuine advance (extending Reed's theorem to digraphs) with a novel technique (vertex identifications for recovering flexibility in tight dense sets). Independent verification of the full argument, especially the LLL dependency structure, would strengthen confidence but the internal logic is sufficiently coherent to warrant the current verdict.","tokens_in":32563,"tokens_out":1001,"duration_ms":1131201,"concrete_test":"Formalize the distance-preservation claim: prove that for any two vertices s, s' at distance d in D's underlying graph, their corresponding vertices in D⋆ are at distance at most 3d. Specifically check the case where the shortest path between s and s' passes through multiple identified pairs in different tight dense sets — does the 'common neighbor' property from Claim 26 suffice when two consecutive identifications occur on the same path? If the factor exceeds 3, recompute whether (∆9) still holds with the corrected exponent.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof's central innovation is identifying pairs of exceptional vertices in tight dense sets to create repeated colors in savior neighborhoods. This requires D⋆ to remain well-behaved: specifically, Claim 29 bounds degrees in D⋆ by Δ+31b, using Claim 26 which states that matched pairs u,v in M⋆_i satisfy |N±(u)∩N±(v)| ≥ Δ−29b+2. Claim 26 follows from: |N±(u)∩N±(v)| ≥ |X_i| − |X_i∖N±(u)| − |X_i∖N±(v)| > |X_i| − 26b ≥ Δ−29b+2 (using tightness |X_i| ≥ Δ−3b+2 and Claim 25 giving |X_i∖N±(u)| < 13b). The bound |X_i∖N±(u)| < 13b comes from u ∈ U⋆_i being chosen in X_i∖R_i, where R_i = {x ∈ X_i : |X_i∖N±(x)| ≥ 13b}. This is internally consistent. However, the entire probabilistic analysis then requires that the bad events have polynomially bounded dependency (§4.5.3), which uses the fact that D⋆ preserves distances up to a factor of 3. The distance-preservation argument is stated informally: 'whenever two vertices are identified, they have at least one neighbor in common' (from Claim 26), so distance-6 in D maps to distance-at-most-2 in D⋆, and the factor-3 comes from the round-trip. This is the least formalized step in an otherwise detailed proof. If the distance preservation factor is even slightly worse (say 4 instead of 3), the dependency count in the LLL becomes (2Δ)^{16} instead of (2Δ)^{12}, and inequality (∆9) — exp(log²(Δ)) ≥ 2^{19}·(Δ+b+1)^{13} — would need to be replaced by a bound with exponent 17 instead of 13, which may still hold but has not been verified. The concern is whether the informal distance-preservation argument is actually correct as stated, since it is the one place where the geometric structure of identifications matters most.","agreement_with_reader":"partial"},"referee_report":{"model":"glm-5.2","summary":"The paper proves a directed analogue of Reed's classical result (Corollary 3 in the manuscript) on coloring graphs with $k$ colors when the clique number is bounded. Specifically, Theorem 7 (restated as Theorem 17) shows that for every fixed integer $b$, there exists a threshold $Delta_b$ such that every digraph $D$ with $tilde{Delta}(D) geq Delta_b$ and biclique number $overleftrightarrow{omega}(D) leq tilde{Delta}(D) - 2b$ satisfies $vec{chi}(D) leq tilde{Delta}(D) - b$, where $tilde{Delta}(D) = max_v sqrt{d^+(v) cdot d^-(v)}$. The result is shown to be tight via a blowing-up construction. The proof combines a Dense Decomposition Lemma (from [16]), structural analysis of dense sets via the notions of saviors and rescuers, vertex identifications in tight dense sets to create an auxiliary digraph $D^star$, and a probabilistic coloring argument via the Lovász Local Lemma.","tokens_in":32891,"tokens_out":13505,"duration_ms":418021,"significance":"This is a substantial contribution to the directed coloring program. It extends a classical theorem of Reed to the directed setting, supports Conjecture 5 (a directed analogue of Reed's conjecture), and the tightness result confirms that the $-2b$ threshold is best possible in the directed case (unlike the undirected case where it is only known to be tight up to $o(b)$ terms). The vertex identification technique introduced for tight dense sets is a novel methodological contribution that may find further applications. The result is also stated for a general class of degree parameters beyond $tilde{Delta}$, adding to its scope. The lower bound construction is explicit and verifiable.","major_comments":[{"comment":"§4.5.3 (Lovász Local Lemma application): The distance-preservation argument for $D^star$ is stated informally. The text asserts that 'whenever two vertices are identified, they have at least one neighbor in common' (from Claim 26), so distance-$2$ in $D^star$ maps to distance-at-most-$6$ in $D$, yielding a dependency radius of $12$ and hence $(2Delta)^{12}$ dependent events. While I believe this factor of $3$ is correct (each hop in $D^star$ involving an identified vertex corresponds to a path of length $leq 3$ in $D$ via the common neighbor), the argument should be stated as a formal lemma or claim with a proof. This is load-bearing: the exponent $13$ in inequality ($Delta_9$) depends on this factor being exactly $3$. I note that even if the factor were slightly larger (say $4$), the LLL would still apply for sufficiently large $Delta$ since $exp(log^2(Delta))$ grows faster than any $n$","section":null}],"minor_comments":[{"comment":"The tightness construction is described in two places with slightly different parametrizations. The abstract states $tilde{Delta}(D) = Delta$ with $Delta geq 3b$, while §1 (page 4) states $tilde{Delta}(D) geq Delta$ with the construction being 'a biclique on $Delta+1$ vertices.' These are consistent (the body uses a different $Delta$ parameter than the abstract), but a brief sentence reconciling the two would help the reader.","section":null},{"comment":"Claim 30: The bound per identified pair is $d^+(v_j) + d^-(v_j) - 2|N^{pm}(u_j) cap N^{pm}(v_j)| leq 2(Delta+b+1) - 2(Delta-29b+2) = 60b - 2$, but the text writes $60b$. This is a valid upper bound (since $60b-2 < 60b$) but the slight looseness should be acknowledged or the exact bound used.","section":null},{"comment":"The list of inequalities ($Delta_1$)–($Delta_9$) is long and the reader must trust that they are all eventually satisfied. A brief remark after the list confirming that each inequality holds for $Delta geq 2^{C b^2}$ for some absolute constant $C$ (which is evident from inspection) would improve readability.","section":null},{"comment":"Figure 1 (page 14): The caption references $R_i$, $U^star_i$, $K^star_i$, and $Y_i$, but the figure itself is not rendered in the text version. If this figure is essential, ensure it is clearly produced in the final version.","section":null},{"comment":"The notation $overleftrightarrow{omega}$ for the biclique number is introduced in §1 but the symbol does not render in all contexts; consider defining it more prominently or using $omega_{leftrightarrow}$ as an alternative.","section":null},{"comment":"Page 4, line on Problem 8: 'It is a consequence of the Directed Brooks Theorem [19] that every oriented graph $D$ with $Delta^+(D) geq 2$ satisfies $vec{chi}(D) leq Delta^+(D)$.' This should perhaps note that the bound $vec{chi}(D) leq Delta^+(D)$ for oriented graphs follows more directly from the greedy coloring argument in §3.2, since oriented graphs have no digons.","section":null}],"recommendation":"minor_revision","confidential_remarks":"The paper builds on two self-citations ([16] and [22]), both co-authored by the present authors. The Dense Decomposition Lemma (Lemma 13) from [16] is the structural foundation of the proof. While this is a legitimate dependency (the lemma is a directed analogue of standard Molloy–Reed decompositions), the correctness of the main theorem is conditional on [16] being correct. I have no reason to doubt [16], but the editor may wish to ensure that [16] is refereed or accepted before this paper is published, or at minimum that the specific instance of the lemma used here (Lemma 9 of [16]) is verified. The stress-test concern about the distance-preservation argument is valid as a presentation issue but does not affect correctness; I verified that even a worse constant would not break the LLL application."},"author_rebuttal":null,"desk_editor":{"model":"glm-5.2","letter":"This paper extends Reed's 1998 result (Corollary 3: graphs with large Δ and small clique number have χ ≤ Δ−b) to digraphs, replacing chromatic number with dichromatic number, maximum degree with the geometric-mean parameter Δ̃, and clique number with biclique number. The main theorem (Theorem 7) states that for every fixed b, every digraph with Δ̃ large enough and biclique number ≤ Δ̃−2b has dichromatic number ≤ Δ̃−b. The bound is tight, which is a nice touch — the extremal construction is simple and convincing. This is a genuine result, not a routine translation. The key methodological novelty is the vertex identification step in Section 4.4: in tight dense sets, where saviors don't have enough external neighbors to guarantee easy coloring, the authors identify pairs of exceptional vertices to force repeated colors into savior neighborhoods. This is a clean idea and the main reason the proof goes through. The structural claims (Claims 21, 23, 27) showing that dense sets contain many saviors are well-argued, and the probabilistic analysis via Lovász Local Lemma is carried out in reasonable detail. The soft spots are real but not fatal. First, the required threshold Δ_b ≥ 2^{Ω(b²)} is far from the linear bound in the undirected case. The authors acknowledge this and say sharper arguments could reduce it, which is honest but means the quantitative result is weak. Second, the proof depends on the Dense Decomposition Lemma (Lemma 13) from a 2025 preprint [16] by overlapping authors. This isn't circular in the logical sense — the lemma is stated as a black box with clear conditions — but its correctness hasn't been independently verified yet. Third, regarding the stress-test concern about distance preservation in D⋆: the argument in Section 4.5.3 is indeed stated informally. The claim is that identifying two vertices with a common neighbor means distance-6 in D maps to distance-at-most-2 in D⋆, giving a factor-3 blowup. This is correct as far as it goes — identified pairs do share neighbors by Claim 26 — but the step is not formalized as carefully as the rest of the proof. If the factor degraded to 4, the LLL dependency bound would need exponent 17 instead of 13 in inequality (∆9), which would likely still hold but hasn't been checked. This is the one place where a careful referee should ask for a more explicit argument. Overall, the central argument holds up. The paper is for specialists in digraph coloring who are comfortable with the probabilistic method and dense decomposition machinery. It deserves a serious referee who can verify the LLL application and the structural decomposition in detail.","headline":"Extends Reed's coloring theorem to digraphs with a clever vertex-identification technique; proof is intricate but largely holds together.","tokens_in":33503,"tokens_out":656,"would_cite":true,"duration_ms":192092,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"glm-5.2","headline":"Δ−b colors suffice for digraphs with small bicliques","keywords":["dichromatic number","digraph coloring","biclique","dense decomposition","vertex identification","Lovász Local Lemma","Reed's theorem","Borodin-Kostochka conjecture"],"falsifier":"An explicit digraph with Δ̃(D) ≥ Δ_b, biclique number at most Δ̃(D) − 2b, and dichromatic number exceeding Δ̃(D) − b, for some fixed b and arbitrarily large Δ̃.","tokens_in":32590,"feed_emoji":"🎨","tokens_out":3647,"duration_ms":156543,"temperature":0.7,"pith_summary":"The paper proves that for every fixed integer b, every digraph D whose maximum geometric-mean degree Δ̃(D) is sufficiently large (relative to b) and whose largest biclique has size at most Δ̃(D) − 2b can have its vertices partitioned into at most Δ̃(D) − b acyclic sets. This is the directed analogue of a classical theorem of Reed for undirected graphs, where the same statement holds with maximum degree replacing Δ̃ and clique number replacing biclique number. The bound is tight: for every b and Δ ≥ 3b, there exists a digraph with Δ̃ = Δ, dichromatic number exactly Δ − b + 1, and largest biclique exactly Δ − 2b + 1. The result supports the authors' broader conjecture that every digraph satisfies χ⃗(D) ≤ ⌈½(Δ̃(D) + 1 + ω↔(D))⌉, a directed version of Reed's conjecture for graphs.","feed_headline":"Δ−b colors suffice for digraphs with small bicliques","feed_subtitle":"The degree-clique tradeoff from undirected graphs carries over via geometric-mean degree, with a matching lower bound.","key_machinery":"Vertex identifications inside tight dense sets create repeated colors in savior neighborhoods, compensating for the lack of external neighbors and allowing a random partial coloring to extend. The Lovász Local Lemma applies because each bad event depends on only polynomially many others, guaranteed by D⋆ preserving distances up to a factor of three.","core_discovery":"The proof combines a dense decomposition — partitioning the digraph into sparse vertices and near-biclique dense sets — with a probabilistic coloring argument on an auxiliary digraph D⋆. The central innovation is vertex identification: inside tight dense sets (those whose bicliques have size Δ̃ − O(b)), carefully chosen pairs of exceptional vertices are merged into single vertices in D⋆. When D⋆ is randomly colored and then partially uncolored wherever a color appears in both the in- and out-neighborhood of a vertex, these identifications force repeated colors in the neighborhoods of savior vertices — vertices that lie in the biclique and have many external neighbors. The repeated colors补偿 (","pith_inferences":["If Conjecture 5 is eventually proven, the threshold Δ_b in this theorem would become unnecessary — the statement would hold for all Δ̃, not just sufficiently large ones, paralleling how Conjecture 4 strengthens Corollary 3 in the undirected case.","The vertex identification technique could potentially apply to oriented graph coloring (Problems 8 and 9 in the paper), where the maximum out-degree Δ⁺ replaces Δ̃, though the authors note this extension remains open.","The tightness construction — blowing up b vertices of a biclique into directed triangles — suggests that the interplay between directed cycles and bicliques is fundamentally more constrained than the undirected interplay between odd cycles and cliques, which may have consequences for the structure of dichromatic-critical digraphs."],"forward_implications":["The directed analogue of Reed's Δ−b coloring theorem holds, confirming that the same degree-versus-clique-number tradeoff governs both directed and undirected coloring.","The biclique threshold Δ̃ − 2b is best possible for digraphs — unlike the undirected case where the threshold may be improvable — because directed cycles inside biclique blow-ups create obstructions with no undirected analogue.","The result provides evidence for Conjecture 5, the directed version of Reed's conjecture χ ≤ ⌈½(Δ + 1 + ω)⌉, which would unify this theorem with the directed Brooks theorem.","The vertex identification technique may transfer to other coloring problems where dense substructures limit the flexibility of probabilistic arguments, particularly in settings where the degree parameter is a geometric or arithmetic mean of in- and out-degrees."],"fun_headline_variants":["Reed's coloring theorem extends to digraphs via biclique bounds","Biclique size controls dichromatic number in directed graphs","Directed version of Reed's Δ−b coloring result is tight","Large bicliques or few colors: directed Reed theorem holds","Dichromatic number bounded when digraphs lack large bicliques"],"cache_read_input_tokens":0,"weakest_assumption_plain":"The entire proof rests on a Dense Decomposition Lemma cited from a 2025 preprint by overlapping authors, which guarantees that every large-degree digraph partitions into sparse vertices and near-biclique dense sets; if this structural decomposition fails to provide the guarantees claimed, the subsequent analysis of saviors, rescuers, and the probabilistic coloring argument collapses.","fun_headline_variants_meta":{"raw":{"variants":["Reed's coloring theorem extends to digraphs via biclique bounds","Biclique size controls dichromatic number in directed graphs","Directed version of Reed's Δ−b coloring result is tight","Large bicliques or few colors: directed Reed theorem holds","Dichromatic number bounded when digraphs lack large bicliques"]},"model":"glm-5.2","effort":"low","cost_usd":0.0,"raw_usage":{"total_tokens":644,"prompt_tokens":572,"completion_tokens":72,"prompt_tokens_details":null},"tokens_in":572,"tokens_out":72,"duration_ms":43798,"temperature":1.0,"reasoning_tokens":null,"cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-09T22:45:06.069800+00:00","model_set":{"reader":"glm-5.2"},"falsifier":"An explicit digraph with Δ̃(D) ≥ Δ_b, biclique number at most Δ̃(D) − 2b, and dichromatic number exceeding Δ̃(D) − b, for some fixed b and arbitrarily large Δ̃.","supporting_citations":[],"review_version":1}