{"id":"1d3ec362-8e11-471c-8eaf-082e542c78aa","arxiv_id":"2608.10687","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":1,"one_line_summary":"New 0_k-graphs with degrees k and 2k show chi'_k(G) can exceed k by a constant fraction, disproving two conjectures that predicted k+o(k) or k+C colors.","lead":"This paper builds graphs whose vertex degrees are all multiples of k, but which need about 1.17k colors in a modular edge coloring, not the roughly k colors predicted by two recent conjectures. The examples are connected bipartite, and also nonbipartite, for every k, so both conjectures are false.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: Lemma 3.1's counting is sound and both example families satisfy every hypothesis needed for the lower bound.","rationale":"The paper's goal is to disprove two conjectures by constructing 0_k-graphs whose mod-k chromatic index exceeds k by a positive linear amount. The proof strategy is coherent: Lemma 2.1 forces exactly k colors per vertex for any coloring with fewer than 2k colors, with exactly one heavy color at each 2k-vertex. Lemma 3.1 then counts color appearances on the X-side. I checked the algebraic steps carefully. The degree-sum identity is correct because edges between X and Y cancel, while internal edges contribute twice. The bound for heavy colors uses only N_Y^c <= 2k and e_Y^c >= 0. The summation over colors and the inequalities q_h <= t and sum e_X^c <= p_X are all valid, yielding s(2k-t) >= t(k-t) - 2p_X. The finite-difference computation in Lemma 3.2 is correct: the numerator factors with roots theta_k and (4k-1+sqrt(8k^2+1))/2, and the asymptotic t_k/k -> 2 - sqrt(2) gives the stated coefficient. The bipartite construction is a clean complete multipartite arrangement with no X-internal edges, and every vertex has the prescribed degree. The nonbipartite rewiring deletes au and bv and adds ab and uv; this preserves all degrees, keeps the graph simple, creates a triangle, and sets e(F[X]) = 1. No hidden assumption is violated. Minor textual typos, such as the mention of a ceiling when the symbol may be typeset oddly, do not affect the mathematics. The exact-degree hypothesis is the one place where a small perturbation would break the counting, but the constructions are explicitly engineered to satisfy it, so the central claim stands.","tokens_in":6710,"tokens_out":12865,"duration_ms":131710,"concrete_test":"Independently re-derive Lemma 3.1 from the degree-sum identity and verify both example families against every hypothesis: for B_{k,t_k} confirm |X|=2k-t_k, |Y|=2k, degree set {k,2k}, and p_X=0; for F_k confirm degree preservation and p_X=1. If either family fails a hypothesis, the counterexample sequence collapses; I expect both to pass.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I find no load-bearing gap in the central argument. The proof hinges on Lemma 3.1, which needs every vertex outside A to have degree exactly k; this is what prevents heavy colors at vertices of Y or X\\A and keeps the identity N_X^c + k mu_c - N_Y^c = 2(e_X^c - e_Y^c) valid. The counting step is correct: for a heavy color c, N_X^c <= 2k - k mu_c + 2e_X^c follows from N_Y^c <= 2k and e_Y^c >= 0, and summing over colors gives s(2k-t) >= t(k-t) - 2p_X. The optimization of g_k(t) is also correct, with t_k/k -> 2 - sqrt(2) and g_k(t_k)/k -> 3 - 2 sqrt(2). The bipartite construction has p_X = 0 and the rewired nonbipartite construction preserves all degrees with p_X = 1; both are connected, simple, and 0_k with degree set {k, 2k}. The exact-degree condition is indeed the most delicate assumption, but it is satisfied by the constructions, so it is a limitation of the lemma, not a defect in the counterexamples.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the modular chromatic index chi'_k(G), the minimum number of colors in an edge-coloring of a graph such that every nonzero color-degree is congruent to 1 modulo k. The authors disprove two conjectures: Conjecture 1.2 of Berthe et al., which states that every 0_k-graph satisfies chi'_k(G) <= k + o(k), and the earlier Conjecture 1.1 of Botler, Colucci, and Kohayakawa, which predicts chi'_k(G) <= k + C for an absolute constant C. The main technical contribution is Lemma 3.1, a counting lemma that gives a lower bound on chi'_k(G) for graphs with a vertex partition X union Y, with |X| = 2k - t, |Y| = 2k, t vertices of X of degree 2k, all other vertices of degree k, and e(G[X]) = p_X. Optimizing the free parameter t (Lemma 3.2) yields t_k/k -> 2 - sqrt(2) and a lower bound of (4 - 2*sqrt(2) + o(1))k under the condition p_X = o(k^2). The authors then construct connected bipartite and connected nonbipartite 0_k-graphs with degree set {k, 2k} satisfying this condition, giving explicit counterexamples to both conjectures. The paper closes with two open problems about optimality of the constant 4 - 2*sqrt(2).","tokens_in":6873,"tokens_out":10640,"duration_ms":100929,"significance":"If correct, the paper settles two open conjectures in the negative with explicit, verifiable constructions rather than nonconstructive existence arguments. The lower-bound proof is self-contained and relies only on a clean counting argument, and the examples are simple enough to check directly. The exact-degree condition in Lemma 3.1 is delicate, and the authors carefully engineer both example families to satisfy it: the bipartite construction has p_X = 0, and the rewired nonbipartite construction preserves all degrees while introducing exactly one internal edge in each part, giving p_X = 1. The improvement from the earlier lower bound of (3/2)k for general graphs to a linear coefficient exceeding k for 0_k-graphs is noteworthy, and the explicit nature of the constructions makes the counterexamples easy to verify. The authors also honestly note that their lower-bound technique does not rule out stronger bounds for other degree patterns, which is appropriate.","major_comments":[],"minor_comments":[{"comment":"The manuscript has numerous LaTeX spacing and rendering issues (for example, '0_k-graph', 'chi'_k(G)', and 'k≥2' appear with missing spaces), which should be corrected before publication.","section":"Throughout"},{"comment":"Reference [13] has an incomplete title: 'Covering the edges of a graph by. . .' should be replaced with the full title, and the bibliographic details should be checked against the actual publication.","section":"References"},{"comment":"The short paragraph immediately following the proof of Lemma 3.1, which observes that the degree sums over X and Y are both 2k^2 and concludes e(G[X]) = e(G[Y]), is not used elsewhere in the paper; consider deleting it or explicitly labeling it as an observation.","section":"Section 3 (after Lemma 3.1)"}],"recommendation":"minor_revision","confidential_remarks":"The paper is mathematically sound and the counterexample constructions are convincing. The only issues I found are editorial: the incomplete reference [13] and a number of formatting glitches. I recommend acceptance after these minor revisions are made."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a real disproof of both conjectures, and the proof is in good shape. The counting in Lemma 3.1 is sound, the optimization is correct, and the two example families are explicit and satisfy every hypothesis. I agree with the stress-test read: the exact-degree condition is the one delicate assumption, but the constructions meet it, so it is a limitation of the lemma rather than a gap in the counterexamples.\n\nWhat is actually new: Liu, Xu, and Yang had already killed Conjecture 1.1, but their examples are not 0_k-graphs, and they explicitly left the 0_k case open. This paper closes that door by giving 0_k-graphs with degree set {k,2k} that need (4−2√2+o(1))k colors, so the gap chi'_k−k is linear. The heavy-color counting trick and the coefficient 4−2√2 are not in the earlier literature, as far as I can tell. The constructions are simple—bipartite with one part split correctly, and a two-edge swap that adds a triangle—but they are exactly what the situation requires. The paper is also honest: it states open problems on sharpness rather than claiming the coefficient is optimal.\n\nSoft spots: mostly cosmetic. Eq. (1) is a max with a nonnegative floor term; the proof of Theorem 1.3 refers to 'inside the ceiling' when there is no ceiling symbol, which should be fixed. The degree condition d_G(v)=k for all v outside A is indeed essential to Lemma 3.1—it is what prevents outside vertices from carrying heavy colors. That is a genuine restriction on the method, but since the counterexample families satisfy it, the disproof stands. The lower bound is asymptotic, but the conjectures are asymptotic/constant statements, so that is the right regime. I do not see any circularity or fitted parameters: t_k is an explicit maximizer, and the constructions are built first and then bounded.\n\nVerdict: this is a good counterexample paper. It deserves a serious referee and, after minor corrections, acceptance. I would take it to our reading group and cite it if I worked on modular colorings.","headline":"Solid disproof of two modular edge-coloring conjectures; the counting argument is correct and the examples satisfy the hypotheses.","tokens_in":7519,"tokens_out":2322,"would_cite":true,"duration_ms":22896,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C15","05C70"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that some 0_k-graphs need at least (4-2\\sqrt{2}+o(1))k colors in a mod-k edge coloring, refuting two conjectures.","keywords":["mod k chromatic index","0_k-graph","modular edge coloring","counterexample","degree set {k,2k}","bipartite graph","lower bound","chromatic index"],"falsifier":"Compute or bound $\\chi'_k$ for the explicit family $B_{k,t_k}$ of Section 4 for increasing $k$. If the ratio $\\chi'_k/k$ ever dips below $4-2\\sqrt{2}$, the lower bound is false.","tokens_in":1526,"feed_emoji":"🎨","tokens_out":4502,"duration_ms":103634,"temperature":0.7,"pith_summary":"The paper disproves two conjectures on the mod-$k$ chromatic index $\\chi'_k(G)$: the conjecture of Berthe et al. that every $0_k$-graph satisfies $\\chi'_k(G)\\le k+o(k)$, and the earlier conjecture of Botler et al. that $\\chi'_k(G)\\le k+C$ for an absolute constant $C$. The authors construct connected bipartite $0_k$-graphs, and separately connected nonbipartite $0_k$-graphs, whose vertices have degree only $k$ or $2k$, and prove that these graphs need at least $(4-2\\sqrt{2}+o(1))k$ colors, roughly $1.17k$. Since the excess above $k$ grows linearly in $k$, neither conjecture can hold.","feed_headline":"Some k-divisible graphs need 1.17k colors in edge coloring","feed_subtitle":"Connected bipartite and nonbipartite counterexamples refute two conjectured upper bounds.","key_machinery":"The argument rests on Lemma 3.1, which counts colors by comparing degree sums inside $X$ and $Y$. Under a coloring with fewer than $2k$ colors, Lemma 2.1 forces exactly $k$ colors to appear at every vertex, and at a $2k$-vertex exactly one of those colors has color degree $k+1$, called the heavy color. For each color $c$, the identity $N_X^c+k\\mu_c-N_Y^c=2(e_X^c-e_Y^c)$ links the numbers of vertices where $c$ appears to the internal edges of that color. Summing this over colors gives a lower bound $q\\ge k+(t(k-t)-2p_X)/(2k-t)$. Choosing $t_k\\approx(2-\\sqrt{2})k$ maximizes the ratio $t(k-t)/(2k-t)$, yielding the coefficient $3-2\\sqrt{2}$ for the excess over $k$.","core_discovery":"The central claim is Theorem 1.3: with a suitable integer $t_k$ satisfying $t_k/k\\to 2-\\sqrt{2}$, every graph $G_k$ with partition $V(G_k)=X_k\\cup Y_k$, $|X_k|=2k-t_k$, $|Y_k|=2k$, where $t_k$ vertices of $X_k$ have degree $2k$, every other vertex has degree $k$, and $e(G_k[X_k])=o(k^2)$, must have $\\chi'_k(G_k)\\ge(4-2\\sqrt{2}+o(1))k$. Section 4 constructs such graphs as connected bipartite graphs and as connected nonbipartite graphs, with $e(G_k[X_k])$ equal to $0$ or $1$. Therefore the difference $\\chi'_k(G_k)-k$ is at least $(3-2\\sqrt{2}+o(1))k$, a linear function of $k$, contradicting both conjectures.","pith_inferences":["The construction suggests that degree sets richer than $\\{k,2k\\}$ may force even larger lower bounds; the counting argument only uses the heavy-color structure at the $2k$-vertices.","The same degree-sum identity could be adapted to other moduli or other prescribed degree sets, since the modularity condition is what creates the heavy-color contribution.","One could test the asymptotic by computing exact values of $\\chi'_k$ for the explicit family $B_{k,t_k}$ at small $k$; the expected excess is $(3-2\\sqrt{2})k$ plus lower-order terms."],"forward_implications":["Conjecture 1.2 is false: some $0_k$-graphs require $k+\\Omega(k)$ colors, so the gap above the local lower bound is linear.","Conjecture 1.1 is false even for connected bipartite $0_k$-graphs with degree set $\\{k,2k\\}$, so no absolute constant $C$ bounds $\\chi'_k(G)-k$.","The same lower bound holds for connected nonbipartite $0_k$-graphs with the same degree set.","The coefficient $4-2\\sqrt{2}$ is the largest obtainable from Lemma 3.1; the paper leaves open whether it is optimal for this degree pattern."],"supporting_citations":[{"why":"States Conjecture 1.2, which the constructed $0_k$-graphs disprove.","marker":"[3]"},{"why":"States Conjecture 1.1, which the same examples also disprove.","marker":"[4]"},{"why":"Gives the earlier lower bound for non-$0_k$-graphs and establishes the open status of the $0_k$-graph case.","marker":"[7]"}],"fun_headline_variants":["Modular edge coloring conjectures fall to 1.17k lower bound","Counterexamples force 1.17k colors for k-divisible graphs","Linear gap disproves two edge coloring conjectures","Connected graph counterexamples refute modular coloring bound","k-divisible graphs need at least 1.17k edge colors"],"cache_read_input_tokens":9600,"weakest_assumption_plain":"The proof assumes every vertex outside the small set $A$ has degree exactly $k$, so no vertex of $Y$ can carry a heavy color; the counting bound would need an extra term if any such vertex had degree $2k$.","fun_headline_variants_meta":{"raw":{"variants":["Modular edge coloring conjectures fall to 1.17k lower bound","Counterexamples force 1.17k colors for k-divisible graphs","Linear gap disproves two edge coloring conjectures","Connected graph counterexamples refute modular coloring bound","k-divisible graphs need at least 1.17k edge colors"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000491,"raw_usage":{"total_tokens":2451,"prompt_tokens":1017,"completion_tokens":1434,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":633,"completion_tokens_details":{"reasoning_tokens":1361}},"tokens_in":633,"tokens_out":1434,"duration_ms":11368,"temperature":1.0,"reasoning_tokens":1361,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T19:25:53.347520+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute or bound $\\chi'_k$ for the explicit family $B_{k,t_k}$ of Section 4 for increasing $k$. If the ratio $\\chi'_k/k$ ever dips below $4-2\\sqrt{2}$, the lower bound is false.","supporting_citations":[{"cited_title":"Berthe, M","cited_arxiv_id":null,"evidence_quote":"States Conjecture 1.2, which the constructed $0_k$-graphs disprove."},{"cited_title":"Botler, L","cited_arxiv_id":null,"evidence_quote":"States Conjecture 1.1, which the same examples also disprove."},{"cited_title":"Linear Lower Bounds for the Modular Chromatic Index","cited_arxiv_id":"2608.02239","evidence_quote":"Gives the earlier lower bound for non-$0_k$-graphs and establishes the open status of the $0_k$-graph case."}],"review_version":1}