Pith. sign in

REVIEW 4 minor 48 references

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.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-04 10:52 UTC pith:Q64RBYG2

load-bearing objection A self-contained disproof of the BCK conjecture with explicit geometric constructions; referee it, but fix the reference list first.

arxiv 2608.02239 v1 pith:Q64RBYG2 submitted 2026-08-03 math.CO

Linear Lower Bounds for the Modular Chromatic Index

Xiao-Chuan Liu , Boyan Xu , Xu Yang This is my paper
classification math.CO MSC 05C15
keywords mod k chromatic index1 mod k edge-coloringedge-coloringbipartite graphscodegree obstructionlinear lower boundaffine hyperplane constructionprobabilistic method
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

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.

Core claim

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

What carries the argument

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.

Load-bearing premise

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.

What would settle it

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.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • 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.

Where Pith is reading between the lines

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

  • 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 4 minor

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.

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.

minor comments (4)
  1. [Section 2, proof of Theorem 1.4] 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.
  2. [Section 2, Theorem 1.4, Case 2] 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.
  3. [Section 2, Lemma 2.1] 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.
  4. [Throughout] There are a number of OCR/typographical artifacts in the preprint (e.g., '1 modk' and superscript spacing). These do not affect the mathematics.

Circularity Check

0 steps flagged

No significant circularity; central lower bounds are derived from an explicit codegree obstruction and self-contained constructions.

full rationale

The paper's central claims are self-contained. Lemma 2.1 isolates a codegree condition, and each construction (cyclic intervals, affine hyperplanes over F_3, structured random perturbation) verifies that condition explicitly. The equality Δ(G)=χ'_k(G)=n follows from the lower bound in Lemma 2.1 plus König's line-coloring theorem for the upper bound, not from any fitted parameter. In Theorem 1.4 the constants T, A, s, a are chosen to make concentration estimates hold and to produce the final error O((k log k)^{1/3}); these are proof artifacts rather than data fits. Prior work (Pyber, Scott, Botler–Colucci–Kohayakawa, Nweit–Yang) appears only as context and upper-bound benchmarks; no load-bearing argument reduces to a self-citation. The appendix's finite-geometric construction is explicitly attributed to Thomason and reproduced with full verification. I found no step where a prediction is equivalent to an input by definition, no fitted quantity renamed as a prediction, and no uniqueness claim imported from the authors' prior work.

Axiom & Free-Parameter Ledger

1 free parameters · 4 axioms · 0 invented entities

No free parameters are fitted to empirical data. The constant 10 in Theorem 1.4 is an explicit proof constant (any large enough constant would do), and the quantities a, s, r, t, d are construction variables determined by k. The paper relies on standard theorems: König's edge-coloring theorem, Hoeffding's inequality, the prime number theorem, and finite-field hyperplane counting. No invented entities are introduced.

free parameters (1)
  • Constant 10 in Theorem 1.4 bound = 10
    Chosen by hand so the union-bound error fits under 10T; the theorem only needs existence of some absolute constant, so this is a proof artifact, not a fit to data.
axioms (4)
  • standard math König's line-coloring theorem: every bipartite graph has edge-chromatic number equal to its maximum degree.
    Used in Lemma 2.1 to obtain the upper bound χ'_k(G) ≤ Δ(G) when Δ(G)=n.
  • standard math Hoeffding's inequality for sums of independent Bernoulli variables and for hypergeometric sampling.
    Used in Theorem 1.4 to concentrate R_B, Y_u, Z_uv.
  • standard math Prime number theorem and the existence of a prime q with k_q = (1-o(1))k.
    Used in Appendix A to lift the special-sequence construction to arbitrary sufficiently large k.
  • standard math Counting of affine hyperplanes in F_3^m (number of parallel classes, hyperplanes containing a point or a pair).
    Used in Theorems 1.3 and 1.4 to compute degrees and common neighborhoods.

pith-pipeline@v1.3.0-daily-deepseek · 8814 in / 36061 out tokens · 244231 ms · 2026-08-04T10:52:56.762184+00:00 · methodology

0 comments
read the original abstract

Let $k\geq2$ be an integer. A $1\bmod k$ edge-coloring of a graph $G$ is an edge-coloring in which every nonzero degree in each color class is congruent to $1$ modulo $k$. Let $\chi'_k(G)$ denote the minimum number of colors required, and let $\chi'_k$ be the supremum of $\chi'_k(G)$ over all finite simple graphs $G$. Botler, Colucci, and Kohayakawa conjectured that there exists an absolute constant $C$ such that $\chi'_k(G)\leq k+C$ for every $k$ and every $G$. We disprove this conjecture, even within the class of bipartite graphs. More precisely, for all integers $c\geq0$ and $k\geq3c+2$, we construct a finite simple bipartite graph $G_{k,c}$ satisfying $\chi'_k(G_{k,c})=k+c+1$. Consequently, $\chi'_k\geq k+\lfloor(k+1)/3\rfloor$ for every $k\geq2$. For $k_m=2\cdot3^{m-1}$, we give an affine-hyperplane construction of a finite simple bipartite graph $G_m$ satisfying $\Delta(G_m)=\chi'_{k_m}(G_m)=3^m=3k_m/2$. More generally, for every sufficiently large $k$, we construct a finite simple bipartite graph $G_k$ such that $\Delta(G_k)=\chi'_k(G_k)\geq3k/2-10(k\log k)^{1/3}$. Our proofs combine a codegree obstruction with explicit cyclic and affine-geometric constructions and a structured random perturbation.

discussion (0)

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

Reference graph

Works this paper leans on

48 extracted references · 3 linked inside Pith

  1. [1]

    Journal of Combinatorial Theory, Series B , volume=

    Regular subgraphs of almost regular graphs , author=. Journal of Combinatorial Theory, Series B , volume=. 1984 , publisher=

    1984

  2. [2]

    Doklady Akademii Nauk , volume=

    Regular subgraphs of regular graphs , author=. Doklady Akademii Nauk , volume=. 1982 , organization=

    1982

  3. [3]

    Studia Sci

    On a problem of graph theory , author=. Studia Sci. Math. Hungar. , volume=

  4. [4]

    2015 , publisher=

    Catalan numbers , author=. 2015 , publisher=

    2015

  5. [5]

    , author=

    Covering the edges of a graph by ... , author=. Sets, Graphs and Numbers, Colloquia Mathematica Societatis J

  6. [6]

    Journal of Graph Theory , volume=

    Covering the edges of a graph by three odd subgraphs , author=. Journal of Graph Theory , volume=. 2006 , publisher=

    2006

  7. [7]

    European Journal of Combinatorics , volume=

    Odd decompositions and coverings of graphs , author=. European Journal of Combinatorics , volume=. 2021 , publisher=

    2021

  8. [8]

    North-Holland Mathematics Studies , volume=

    Pseudo-random graphs , author=. North-Holland Mathematics Studies , volume=. 1987 , publisher=

    1987

  9. [9]

    Yoshiharu Kohayakawa , year =

  10. [10]

    , title =

    Scott, Alexander D. , title =. Discrete Mathematics , volume =. 1997 , doi =

    1997

  11. [11]

    Graphs and Combinatorics , volume=

    Ramsey theory and bandwidth of graphs , author=. Graphs and Combinatorics , volume=. 2001 , publisher=

    2001

  12. [12]

    arXiv preprint arXiv:2112.13119 , year=

    Turan Number for certain subdivisions , author=. arXiv preprint arXiv:2112.13119 , year=

    Pith/arXiv arXiv

  13. [13]

    Journal of Combinatorial Theory, Series B , volume=

    Extremal graphs with no C4's, C6's, or C10's , author=. Journal of Combinatorial Theory, Series B , volume=. 1991 , publisher=

    1991

  14. [14]

    Journal of the European Mathematical Society , volume=

    Rational exponents in extremal graph theory , author=. Journal of the European Mathematical Society , volume=

  15. [15]

    SIAM Journal on Discrete Mathematics , volume=

    On Modular Edge Colorings of Graphs , author=. SIAM Journal on Discrete Mathematics , volume=. 2026 , publisher=

    2026

  16. [16]

    The mod k chromatic index of graphs is

    Botler, F. The mod k chromatic index of graphs is. Journal of Graph Theory , volume=. 2023 , publisher=

    2023

  17. [17]

    Discrete Mathematics & Theoretical Computer Science , volume=

    On the mod k chromatic index of graphs , author=. Discrete Mathematics & Theoretical Computer Science , volume=. 2024 , publisher=

    2024

  18. [18]

    arXiv preprint arXiv:2103.10200, to appear, SIAM Journal on Discrete Mathematics , year=

    On Turan Number for generalized Theta Graph , author=. arXiv preprint arXiv:2103.10200, to appear, SIAM Journal on Discrete Mathematics , year=

    Pith/arXiv arXiv

  19. [19]

    On the structure of linear graphs , author=. Bull. Amer. Math. Soc. , volume=

  20. [20]

    Colloquia Mathematica Societatisj

    On some extremal problems in graph theory , author=. Colloquia Mathematica Societatisj

  21. [21]

    Jiang, Tao and Seiver, Robert , journal=. Tur. 2012 , publisher=

    2012

  22. [22]

    Journal of Combinatorial Theory, Series B , volume=

    Graphs without theta subgraphs , author=. Journal of Combinatorial Theory, Series B , volume=. 2019 , publisher=

    2019

  23. [23]

    Bukh, Boris and Tait, Michael , journal=. Tur. 2020 , publisher=

    2020

  24. [24]

    Bulletin of the London Mathematical Society , volume=

    Graphs with few paths of prescribed length between any two vertices , author=. Bulletin of the London Mathematical Society , volume=. 2019 , publisher=

    2019

  25. [25]

    Combinatorics, Probability & Computing , volume=

    A Bound on the Number of Edges in Graphs Without an Even Cycle , author=. Combinatorics, Probability & Computing , volume=. 2017 , publisher=

    2017

  26. [26]

    2020 , journal=

    New Upper Bound on Extremal Number of Even Cycles , author=. 2020 , journal=

    2020

  27. [27]

    2020 , journal=

    Extremal numbers of cycles revisited , author=. 2020 , journal=

    2020

  28. [28]

    SIAM Journal on Discrete Mathematics , volume=

    The extremal number of the subdivisions of the complete bipartite graph , author=. SIAM Journal on Discrete Mathematics , volume=. 2020 , publisher=

    2020

  29. [29]

    Combinatorica , volume=

    More on the extremal number of subdivisions , author=. Combinatorica , volume=. 2021 , publisher=

    2021

  30. [30]

    On the rational Tur

    Kang, Dong Yeap and Kim, Jaehoon and Liu, Hong , journal=. On the rational Tur. 2021 , publisher=

    2021

  31. [31]

    Jiang, Tao and Ma, Jie and Yepremyan, Liana , journal=. On Tur. 2022 , publisher=

    2022

  32. [32]

    arXiv preprint arXiv:2203.03375 , year=

    Rational exponents near two , author=. arXiv preprint arXiv:2203.03375 , year=

    Pith/arXiv arXiv

  33. [33]

    Many Tur

    Jiang, Tao and Qiu, Yu , journal=. Many Tur. 2023 , publisher=

    2023

  34. [34]

    Combinatorica , volume=

    On the combinatorial problems which I would most like to see solved , author=. Combinatorica , volume=. 1981 , publisher=

    1981

  35. [35]

    Combinatorica , volume=

    On a class of degenerate extremal graph problems , author=. Combinatorica , volume=. 1983 , publisher=

    1983

  36. [36]

    Mat.Fiz.Lapok (Hungarian) , volume=

    On an extremal problem in graph theory , author=. Mat.Fiz.Lapok (Hungarian) , volume=

  37. [37]

    2008 , publisher=

    Graph Theory (graduate texts in mathematics 244) , author=. 2008 , publisher=

    2008

  38. [38]

    Journal of Combinatorial Theory, Series B , volume=

    Cycles of even length in graphs , author=. Journal of Combinatorial Theory, Series B , volume=. 1974 , publisher=

    1974

  39. [39]

    On the Tur

    F. On the Tur. Advances in Mathematics , volume=. 2006 , publisher=

    2006

  40. [40]

    The history of degenerate (bipartite) extremal graph problems , author=. Erd. 2013 , publisher=

    2013

  41. [41]

    2011 , publisher=

    Factors and factorizations of graphs: Proof techniques in factor theory , author=. 2011 , publisher=

    2011

  42. [42]

    Journal of Graph Theory , volume=

    Coverability of graph by three odd subgraphs , author=. Journal of Graph Theory , volume=. 2019 , publisher=

    2019

  43. [43]

    Journal of Graph Theory , volume=

    On the eulericity of a graph , author=. Journal of Graph Theory , volume=. 1978 , publisher=

    1978

  44. [44]

    Journal of Graph Theory , volume=

    Odd 4-edge-colorability of graphs , author=. Journal of Graph Theory , volume=. 2018 , publisher=

    2018

  45. [45]

    Ars Mathematica Contemporanea , volume=

    Odd edge coloring of graphs , author=. Ars Mathematica Contemporanea , volume=. 2014 , publisher=

    2014

  46. [46]

    preprint , pages=

    Combinatorial optimization , author=. preprint , pages=

  47. [47]

    Journal of Graph Theory , volume=

    Odd edge-colorings of subdivisions of odd graphs , author=. Journal of Graph Theory , volume=. 2023 , publisher=

    2023

  48. [48]

    Botler, F. The mod. Journal of Graph Theory , volume =. 2023 , doi =

    2023