Counterexamples to two conjectures on modular edge colorings of graphs

Abstract

For an integer $k\ge 2$, let ${\chi }_k^{\prime }(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(\mathrm{mod}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^{\prime }(G)\le 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^{\prime }(G)\ge (4-2\sqrt{2}+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^{\prime }(G)\le k+C$ for some absolute constant $C$.

arXiv comment10 pages, 2 figures