Linear Lower Bounds for the Modular Chromatic Index

Abstract

Let $k\ge 2$ be an integer. A $1\mathrm{mod}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 $\ddot{I}{‡}_k^{\prime }(G)$ denote the minimum number of colors required, and let $\ddot{I}{‡}_k^{\prime }$ be the supremum of $\ddot{I}{‡}_k^{\prime }(G)$ over all finite simple graphs $G$. Botler, Colucci, and Kohayakawa conjectured that there exists an absolute constant $C$ such that $\ddot{I}{‡}_k^{\prime }(G)\le 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\ge 0$ and $k\ge 3c+2$, we construct a finite simple bipartite graph $G_{k,c}$ satisfying $\ddot{I}{‡}_k^{\prime }(G_{k,c})=k+c+1$. Consequently, $\ddot{I}{‡}_k^{\prime }\ge k+\lfloor (k+1)/3\rfloor$ for every $k\ge 2$. For $k_m=2\cdot 3^{m-1}$, we give an affine-hyperplane construction of a finite simple bipartite graph $G_m$ satisfying $\hat{I}”(G_m)=\ddot{I}{‡}_{k_m}^{\prime }(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 $\hat{I}”(G_k)=\ddot{I}{‡}_k^{\prime }(G_k)\ge 3k/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.

11 pages