Abstract

Given a graph G and an integer k ≥ 2, let χ′ₖ(G) denote the minimum number of colours required to colour the edges of G so that, in each colour class, the subgraph induced by the edges of that colour has all non-zero degrees congruent to 1 modulo k. In 1992, Pyber proved that χ′₂(G) ≤ 4 for every graph G and asked whether χ′ₖ(G) can be bounded solely in terms of k for every k ≥ 3. This question was answered in 1997 by Scott, who showed that χ′ₖ(G) ≤ 5k² log k, and further asked whether χ′ₖ(G) grows only linearly with k. Recently, Botler, Colucci, and Kohayakawa (2023) answered Scott’s question affirmatively, proving that χ′ₖ(G) ≤ 198k − 101, and conjectured that the multiplicative constant could be reduced to 1. A step toward this conjecture was made in 2024 by Nweit and Yang, who improved the bound to χ′ₖ(G) ≤ 177k − 93.In this work, we further improve the multiplicative constant to 9. More specifically, we show that χ′ₖ(G) ≤ 7k o(k) when k is odd, and χ′ₖ(G) ≤ 9k o(k) when k is even. As part of our proof, we establish that χ′ₖ(G) ≤ k + O(d) for every d-degenerate graph G, a result that plays a central role in our argument.