{"id":"8a5685b3-0081-4a15-b47f-8aa0c41038f4","arxiv_id":"2608.02239","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":1,"one_line_summary":"Bipartite graphs force the mod-k chromatic index to grow as 3k/2, refuting the Botler–Colucci–Kohayakawa conjecture.","lead":"This paper disproves a 2023 conjecture that the mod-k chromatic index stays within an additive constant of k for every graph. The authors construct bipartite graphs whose index reaches 3k/2 - o(k), overturning the predicted k + O(1) behavior.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified","rationale":"The reader accepted the paper with high confidence, and my independent check did not reveal a flaw in the central argument. Lemma 2.1 is the engine of the paper; its uniqueness argument requires n<2k+1, which the reader correctly identified as the most delicate assumption. I verified that every construction in the paper satisfies this condition: Theorem 1.2 has n=k+c+1 with c≤(k−2)/3, Theorem 1.3 has n=3a and k=2a, and Lemma 2.2 explicitly requires n≤2k. The explicit common-neighbor computations are consistent, and the probabilistic construction in Theorem 1.4, though intricate, uses correct Hoeffding thresholds (the integer-valued tail correction makes the displayed deviations exceed s in all cases) and a successful union bound. Appendix A.1 also appears sound; the ceiling in s_q is consistent with the inequality 3s_q−2q≥2. Since the disproof of the BCK conjecture rests on Theorem 1.2 alone, even a hypothetical issue in the refinements would not change the verdict. Therefore I see no reason to alter the reader's ACCEPT.","tokens_in":9031,"tokens_out":33232,"duration_ms":243986,"concrete_test":"Enumerate all affine hyperplane complements in F_3^3 (a=9) and check Eq. (2.1): every pair of distinct points has exactly 2a−1=17 common complements. This directly verifies the codegree count used in Theorem 1.3.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I have no load-bearing objection. The central claim—disproving the Botler–Colucci–Kohayakawa conjecture—is established by the explicit bipartite construction in Theorem 1.2, which is independent of the probabilistic and affine-geometric refinements. The key codegree obstruction (Lemma 2.1) is sound: since n=k+c+1≤2k whenever c<k, a degree-n vertex has a unique heavy color class of size k+1; the exceptional-incidence count c per vertex then forces the n heavy colors of the W-vertices to be distinct. All three constructions respect c<k: Theorem 1.2 uses k≥3c+2, Theorem 1.3 has c=a−1<2a, and Lemma 2.2 forces n≤2k. The common-neighbor counts in Theorems 1.2 and 1.3 check out, including the affine-parallel-class count giving exactly 2c+1 in Eq. (2.1). For Theorem 1.4, the random perturbation is delicate, but the tail inequalities are applied to integer thresholds with the necessary +1 correction, the bound s^2≥9a log a makes the union bound <1, and the final error is at most about 3s/2<9T, within 10T. I found no circular reasoning, missing proof, or unsupported step needed for the main theorems.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies the mod k chromatic index χ'_k and refutes the Botler–Colucci–Kohayakawa conjecture that χ'_k(G) ≤ k + O(1) for all graphs. The main tool is a codegree obstruction (Lemma 2.1): in a bipartite graph with |W|=n=k+c+1, each w∈W of degree n, a set X⊆L of vertices of degree at most k, and pairwise common neighborhoods in X of size at least 2c+1, any 1 mod k edge-coloring forces n distinct colors. Three constructions realize this obstruction: (i) a cyclic construction giving G_{k,c} with χ'_k(G_{k,c})=k+c+1 for all k≥3c+2, hence χ'_k ≥ k+⌊(k+1)/3⌋; (ii) an affine-hyperplane construction over F_3 giving exact χ'_{2·3^{m-1}} = 3^m = 3k/2; and (iii) a structured random perturbation yielding χ'_k ≥ 3k/2 - 10(k log k)^{1/3} for all large k. An appendix gives a deterministic finite-field construction of the same asymptotic form.","tokens_in":9391,"tokens_out":25145,"duration_ms":175968,"significance":"If correct, the results resolve in the negative a conjecture that has guided recent work on modular edge colorings. The constructions are fully explicit for Theorems 1.2 and 1.3, and the probabilistic proof in Theorem 1.4 is careful with quantitative tails; the appendix further provides a deterministic route. The codegree lemma is simple and likely to be reusable. The lower bound establishes that the leading coefficient of χ'_k is at least 3/2, sharply narrowing the possible range from the upper bounds of order 9k. The paper reads as self-contained: prior results are cited only as context, and no parameter is fitted to the target bound.","major_comments":[],"minor_comments":[{"comment":"The symbols for floors in the definitions of ℓ and d (e.g., 'ℓ = \\Y s/2 \\]' and 'd = \\Y t/2 \\]') are typeset ambiguously; please use \\lfloor ... \\rfloor or explicitly define them.","section":"Section 2, proof of Theorem 1.4"},{"comment":"The Hoeffding bound for Y_u is stated without showing the integer-threshold step. Since the event is Y_u > s+t+d, the effective deviation from the mean is at least s+1/2, not merely s; this justifies the displayed exp(-2s^2/(3a)). It would help the reader to spell out this detail.","section":"Section 2, Theorem 1.4, Case 2"},{"comment":"The condition d_G(w)=n<2k+1 is essential for the uniqueness of the heavy color. It follows from c<k, but it might be worth stating explicitly that n≤2k.","section":"Section 2, Lemma 2.1"},{"comment":"There are a number of OCR/typographical artifacts in the preprint (e.g., '1 modk' and superscript spacing). These do not affect the mathematics.","section":"Throughout"}],"recommendation":"accept","confidential_remarks":"The paper is ready for publication in my view. The central claim is a clean counterexample to a published conjecture, the proofs are self-contained, and the appendix strengthens the paper by giving a deterministic alternative. I would be happy to see it accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read it; I agree with your take. The main result is real. It disproves the BCK conjecture, and it does so with explicit bipartite constructions rather than a nonconstructive counting argument. Lemma 2.1 is the right kind of obstruction: the heavy-color uniqueness argument is valid because n = k+c+1 < 2k+1, and every construction respects that constraint. I checked the cycle-complement family for Theorem 1.2 and the affine-hyperplane family over F_3 for Theorem 1.3; the common-neighbor counts come out exactly as claimed. The randomized construction in Theorem 1.4 is the part where I expected trouble, but the case split is clean and the tail bounds are applied with integer thresholds. I did not rederive every constant, but nothing I spot-checked wobbles.\n\nWhat is actually new: no graph with χ'_k ≥ k+3 was previously known, so the lower bound from k+2 to 3k/2 – o(k) is a genuine jump. The open problems at the end are honest and target the right next questions.\n\nSoft spots are minor. Reference [5] has a suspicious author name ('Oothan Nweit'), and [4] is a private communication; both should be fixed before publication. The technique is limited to n < 2k+1, so going beyond 3k/2 would require a different idea. That's not a flaw in the paper, but it is a boundary worth stating.\n\nThis is for anyone working on modular edge coloring or, more broadly, graph decompositions with degree conditions. It deserves a serious referee. I would accept after the reference cleanup and cite it.","headline":"A self-contained disproof of the BCK conjecture with explicit geometric constructions; referee it, but fix the reference list first.","tokens_in":9796,"tokens_out":3898,"would_cite":true,"duration_ms":34961,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C15"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper disproves the conjecture that every graph admits a 1 mod k edge-coloring using at most k plus a fixed constant colors, even when restricted to bipartite graphs.","keywords":["mod k chromatic index","1 mod k edge-coloring","edge-coloring","bipartite graphs","codegree obstruction","linear lower bound","affine hyperplane construction","probabilistic method"],"falsifier":"Find a 1 mod k edge-coloring of the cyclic-interval graph G_{k,c} (with k ≥ 3c+2) using only k+c colors, violating Theorem 1.2; or, for a fixed small k (e.g. k=8, c=2, n=11), compute χ'_8(G_{8,2}) explicitly and check whether it equals 11. A second falsifying observation is a graph satisfying Lemma 2.1's hypotheses with n ≥ 2k for which χ'_k(G) < n, which would show the stated condition n<2k is genuinely load-bearing.","tokens_in":8985,"feed_emoji":"🎨","tokens_out":4618,"duration_ms":34224,"temperature":0.7,"pith_summary":"This paper disproves the conjecture that every graph admits a 1 mod k edge-coloring using at most k plus a fixed constant colors, even when restricted to bipartite graphs. It constructs explicit bipartite graphs whose mod k chromatic index equals k+c+1, which gives a lower bound of k + floor((k+1)/3). Along an infinite sequence of moduli (k = 2·3^{m-1}), the construction yields graphs where the index equals the maximum degree, 3k/2, and for every sufficiently large k a randomized construction gives the same leading coefficient with a (k log k)^{1/3} error. If correct, the paper settles the linear coefficient question: any universal upper bound of the form αk+o(k) must have α ≥ 3/2.","feed_headline":"Edge coloring can require 1.5k colors, not k+constant","feed_subtitle":"New bipartite constructions force k+floor((k+1)/3) colors, and along special moduli 3k/2 colors are necessary.","key_machinery":"Lemma 2.1 (codegree obstruction) is the load-bearing mechanism: under the conditions n=k+c+1<2k+1, every W-vertex (degree n) must have a unique color appearing k+1 times; two W-vertices sharing that heavy color would force at most 2c 'exceptional' edges to cover ≥2c+1 common neighbors in X, where degrees ≤k force all incident colors distinct. This forces n distinct heavy colors, hence χ'_k ≥ n. The constructions—cyclic complements of intervals, affine hyperplane complements over F_3, and their scaled random perturbation—are designed precisely to meet these conditions with Δ=n.","core_discovery":"The central discovery is a codegree obstruction: for a bipartite graph with |W| = n, every w in W degree n, low-degree vertices X, and pairwise codegree in X at least 2c+1 (where n=k+c+1), any 1 mod k coloring must use at least n colors. The proof shows each w must have a unique 'heavy' color occurring k+1 times; if two W-vertices shared a heavy color, their 2c exceptional incidences would be exceeded by their ≥2c+1 common low-degree neighbors, forcing a color repetition at a low-degree vertex. The authors realize this obstruction with cyclic interval complements (giving k+floor((k+1)/3)) and with affine hyperplanes over F_3 (giving exactly 3k/2 along k=2·3^{m-1}), and extend to all large k","pith_inferences":["One implication the authors leave implicit: the obstruction is purely about bipartite graphs with prescribed codegrees, so the true worst-case ratio for all graphs might be larger than 3/2; the same obstruction run at larger n (beyond 2k) would require a new idea.","The authors' open question—whether 3/2 can be attained asymptotically along a sequence, i.e. χ'_k ≤ (3/2 + o(1))k—could be tested by constructing explicit families with n as close to 3k/2 as possible while keeping the codegree condition.","The deterministic Thomason-type construction in the appendix suggests that pseudo-random Cayley graphs may give the same obstruction more efficiently; this could extend the lower bound to arbitrary k without the probabilistic error term.","One might attempt to push the coefficient beyond 3/2 by using triple or higher-order codegree conditions, where the 'heavy color' survival argument could count at a different rate."],"forward_implications":["The k+C conjecture is false, even for bipartite graphs.","For every k ≥ 2, at least k+⌊(k+1)/3⌋ colors may be necessary in some graph.","Along k_m = 2·3^{m-1}, the maximum degree itself, 3k_m/2, is the mod k_m chromatic index of a constructed bipartite graph.","For all sufficiently large k, there is a bipartite graph with mod k chromatic index at least 3k/2 − 10(k log k)^{1/3}.","Consequently any universal upper bound of the form αk + o(k) must have α ≥ 3/2."],"fun_headline_variants":["Modular edge coloring needs k + k/3 colors, not k + constant","Bipartite graphs force modular chromatic index up to 3k/2","Linear lower bounds: modular edge coloring beats k+O(1)","Conjecture false: modular chromatic index can hit 1.5k","New bipartite construction gives modular edge coloring 1.5k"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The proof needs n = k+c+1 < 2k+1, so that a repeated color at a W-vertex has multiplicity exactly k+1 and is unique; if a construction pushes the number of W-vertices n beyond 2k, this uniqueness step fails and the lower-bound argument collapses.","fun_headline_variants_meta":{"raw":{"variants":["Modular edge coloring needs k + k/3 colors, not k + constant","Bipartite graphs force modular chromatic index up to 3k/2","Linear lower bounds: modular edge coloring beats k+O(1)","Conjecture false: modular chromatic index can hit 1.5k","New bipartite construction gives modular edge coloring 1.5k"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000242,"raw_usage":{"total_tokens":1441,"prompt_tokens":904,"completion_tokens":537,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":648,"completion_tokens_details":{"reasoning_tokens":439}},"tokens_in":648,"tokens_out":537,"duration_ms":6770,"temperature":1.0,"reasoning_tokens":439,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T10:52:56.762184+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find a 1 mod k edge-coloring of the cyclic-interval graph G_{k,c} (with k ≥ 3c+2) using only k+c colors, violating Theorem 1.2; or, for a fixed small k (e.g. k=8, c=2, n=11), compute χ'_8(G_{8,2}) explicitly and check whether it equals 11. A second falsifying observation is a graph satisfying Lemma 2.1's hypotheses with n ≥ 2k for which χ'_k(G) < n, which would show the stated condition n<2k is genuinely load-bearing.","supporting_citations":[],"review_version":1}