REVIEW 3 minor 15 references
Counterexamples to two conjectures on modular edge colorings of graphs
T0 review · 0 major / 3 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read 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.
desk verdict Solid disproof of two modular edge-coloring conjectures; the counting argument is correct and the examples satisfy the hypotheses. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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$.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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$.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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).
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.
minor comments (3)
- [Throughout] 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.
- [References] 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 3 (after Lemma 3.1)] 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.
Circularity Check
No significant circularity: the lower bound follows from a counting argument on arbitrary colorings, and the examples satisfy the lemma hypotheses explicitly.
full rationale
The derivation chain is self-contained and non-circular. Lemma 2.1 follows directly from the modular degree condition, and Lemma 3.1 derives the lower bound by counting appearances of colors in an arbitrary optimal chi'_k-coloring with fewer than 2k colors; the key identity N_X^c + k mu_c - N_Y^c = 2(e_X^c - e_Y^c) and the bounds N_Y^c <= 2k and e_Y^c >= 0 give the stated inequality without assuming the conjectures or the desired bound. The sequence t_k in Lemma 3.2 and Theorem 1.3 is an explicit maximizer of the closed-form function g_k(t) = t(k-t)/(2k-t), an optimization over a parameter, not a fitted prediction from data. The bipartite construction in Section 4.1 has p_X = 0 and the rewired nonbipartite construction in Section 4.2 has p_X = 1, both satisfying every vertex-degree and edge-count hypothesis of Theorem 1.3; their lower bounds then follow by applying the lemma, which is a standard use of a lemma rather than a circular reduction. There are no self-citations with overlapping authors, and prior results are used only as background. The paper explicitly notes in Section 3.1 that the coefficient may not be best possible for other degree patterns, and in Section 5 that the sharpness of Lemma 3.1 is open (Problems 5.1 and 5.2); these are honest limitations about optimality, not defects in the derivation. No prediction in the paper reduces by construction to its inputs.
Assumptions & free parameters
free parameters (1)
- t_k (size of the special vertex set A) =
ceil((4k-1-sqrt(8k^2+1))/2)
assumptions (2)
- domain assumption Every finite simple graph admits a chi'_k-coloring with finitely many colors (Scott [14], Section 1).
- standard math For a color subgraph G_c and a vertex set S, the sum of color degrees equals twice internal edges plus boundary edges (the handshaking identity).
Cite this review
Pith. "Pith review of Counterexamples to two conjectures on modular edge colorings of graphs." pith.science (2026). https://pith.science/paper/7WFECPXT
@misc{pith2026260810687,
author = {Pith},
title = {Pith review of: Counterexamples to two conjectures on modular edge colorings of graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/7WFECPXT}},
note = {Machine review of arXiv:2608.10687}
}
abstract
For an integer $k\geq2$, let $\chi_k'(G)$ denote the minimum number of colors in an edge-coloring of a graph $G$ such that every nonzero degree in each color subgraph is congruent to $1\pmod{k}$. A graph is a $0_k$-graph if every vertex degree is divisible by $k$. We disprove a conjecture of Berthe et al.\ (On modular edge colorings of graphs, SIAM J. Discrete Math. 40 (2026) 897--904), which states that $\chi_k'(G)\leq k+o(k)$ for every $0_k$-graph $G$. We prove a lower bound for $0_k$-graphs with degree set $\{k,2k\}$ and a specified vertex partition. With a suitable choice of the part sizes, if the number of edges inside one part is $o(k^2)$, then $\chi_k'(G)\geq(4-2\sqrt2+o(1))k$. This gives connected bipartite and connected nonbipartite counterexamples. In particular, the same examples also disprove the earlier conjecture of Botler, Colucci, and Kohayakawa (The mod $k$ chromatic index of graphs is $O(k)$, J. Graph Theory 102 (2023) 197--200), which states that $\chi_k'(G)\leq k+C$ for some absolute constant $C$.
Figures
Reference graph
Works this paper leans on
-
[1]
N. Alon, S. Friedland, G. Kalai, Regular subgraphs of almost regular graphs, J. Combin. Theory Ser. B 37 (1984) 79–91
work page 1984
-
[2]
R. Atanasov, M. Petruˇ sevski, R. ˇSkrekovski, Odd edge-colorability of subcubic graphs, Ars Math. Contemp. 10 (2016) 359–370
work page 2016
- [3]
- [4]
- [5]
-
[6]
M. Kano, G. Y. Katona, Odd subgraphs and matchings, Discrete Math. 250 (2002) 265–272
work page 2002
-
[7]
X.-C. Liu, B. Xu, X. Yang, Linear lower bounds for the modular chro- matic index, arXiv:2608.02239 (2026). 9
work page Pith review arXiv 2026
-
[8]
B. Luˇ zar, M. Petruˇ sevski, R.ˇSkrekovski, Odd edge coloring of graphs, Ars Math. Contemp. 9 (2015) 277–287
work page 2015
Show all 15 references
-
[9]
Mader, Existenzn-fach zusammenh¨ angender Teilgraphen in Graphen gen¨ ugend grosser Kantendichte, Abh
W. Mader, Existenzn-fach zusammenh¨ angender Teilgraphen in Graphen gen¨ ugend grosser Kantendichte, Abh. Math. Semin. Univ. Hambg. 37 (1972) 86–97
1972
-
[10]
M´ atrai, Covering the edges of a graph by three odd subgraphs, J
T. M´ atrai, Covering the edges of a graph by three odd subgraphs, J. Graph Theory 53 (2006) 75–82
2006
-
[11]
Nweit, D
O. Nweit, D. Yang, On the modkchromatic index of graphs, Discrete Math. Theor. Comput. Sci., 26 (2024), no. 3, Art. 16, 6 pp
2024
-
[12]
Petruˇ sevski, Odd 4-edge-colorability of graphs, J
M. Petruˇ sevski, Odd 4-edge-colorability of graphs, J. Graph Theory 87 (2018) 460–474
2018
-
[13]
Pyber, Covering the edges of a graph by
L. Pyber, Covering the edges of a graph by. . ., in Sets, Graphs and Numbers (Budapest, 1991), Colloq. Math. Soc. J´ anos Bolyai 60, North- Holland, Amsterdam (1992) 583–610
1992
-
[14]
A. D. Scott, On graph decompositions modulok, Discrete Math. 175 (1997) 289–291
1997
-
[15]
Thomassen, Graph factors modulok, J
C. Thomassen, Graph factors modulok, J. Combin. Theory Ser. B 106 (2014) 174–177. 10
2014
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.