On Modular Edge Colourings of Graphs

Gaétan Berthe, Marthe Bonamy, Fábio Botler, Gaia Carenini, Lucas Colucci, Arthur Dumas, Fatemeh Ghasemi, Pedro Mariano Viana Neto · 2025

Read On Modular Edge Colourings of Graphs by Gaétan Berthe, Marthe Bonamy, Fábio Botler, Gaia Carenini, Lucas Colucci, Arthur Dumas, Fatemeh Ghasemi, Pedro Mariano Viana Neto (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-04254.txt.

Introduction

Berthe and co-authors improve a bound on coloring the edges of graphs in a 2025 math paper. The coloring rule asks that in each color class, every vertex with any edge of that color has a degree that leaves remainder one when divided by a fixed number k. A question from the 1990s asked whether the number of colors needed can depend only on k.

Later work answered yes but with a large constant factor. This team cuts that factor to nine, and to seven when k is odd, with a small extra term. A key step shows that for graphs that break down in a simple order, the needed colors stay close to k itself.

Catalog record

CREATORGaétan Berthe, Marthe Bonamy, Fábio Botler, Gaia Carenini, Lucas Colucci, Arthur Dumas, Fatemeh Ghasemi, Pedro Mariano Viana Neto
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE21 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-04254

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On Modular Edge Colourings of Graphs Gaétan Berthe, Marthe Bonamy, Fábio Botler, Gaia Carenini, Lucas Colucci, Arthur Dumas, Fatemeh Ghasemi, Pedro Mariano Viana Neto Abstract Given a graph G G and an integer k ≥ 2 k\geq 2 , let χ k ′ ​ ( G ) \chi^{\prime}_{k}(G) denote the minimum number of colours required to colour the edges of G G such that, in each colour class, the subgraph induced by the edges of that colour has all non-zero degrees congruent to 1 1 modulo k k . In 1992, Pyber proved that χ 2 ′ ​ ( G ) ≤ 4 \chi^{\prime}_{2}(G)\leq 4 for every graph G G , and posed the question of whether χ k ′ ​ ( G ) \chi^{\prime}_{k}(G) can be bounded solely in terms of k k for every k ≥ 3 k\geq 3 . This question was answered in 1997 by Scott, who showed that χ k ′ ​ ( G ) ≤ 5 ​ k 2 ​ log ⁡ k \chi^{\prime}_{k}(G)\leq 5k^{2}\log k , and further asked whether χ k ′ ​ ( G ) = O ⁡ ( k ) \chi^{\prime}_{k}(G)=O(k) . Recently, Botler, Colucci, and Kohayakawa (2023) answered Scott’s question affirmatively proving that χ k ′ ​ ( G ) ≤ 198 ​ k − 101 \chi^{\prime}_{k}(G)\leq 198k-101 , and conjectured that the multiplicative constant could be reduced to 1 1 . A step towards this latter conjecture was made in 2024 by Nweit and Yang, who improved the bound to χ k ′ ​ ( G ) ≤ 177 ​ k − 93 \chi^{\prime}_{k}(G)\leq 177k-93 . In this paper, we further improve the multiplicative constant to 9 9 . More specifically, we prove that there is a function f ∈ o ⁡ ( k ) f\in o(k) for which χ k ′ ​ ( G ) ≤ 7 ​ k + f ⁡ ( k ) \chi^{\prime}_{k}(G)\leq 7k+f(k) if k k is odd, and χ k ′ ​ ( G ) ≤ 9 ​ k + f ⁡ ( k ) \chi^{\prime}_{k}(G)\leq 9k+f(k) if k k is even. In doing so, we prove that χ k ′ ​ ( G ) ≤ k + O ⁡ ( d ) \chi^{\prime}_{k}(G)\leq k+O(d) for every d d -degenerate graph G G , which plays a central role in our proof. Keywords: mod k k -chromatic-index, degenerate graphs, linear upper bound 1 Introduction Throughout this paper, unless otherwise specified, k\geq 2 denotes an integer. All graphs considered are simple, and e(G) denotes the number of edges in a graph G . A \chi^{\prime}_{k} -colouring of G is an edge-colouring of G in which each colour class, i.e., the subgraph induced by its edges, has all vertex degrees congruent to 1\pmod{k} . The mod k chromatic index of G , denoted by \chi^{\prime}_{k}(G) , is the minimum number of colours required for a \chi^{\prime}_{k} -colouring of G . Pyber [ 8 ] proved that \chi^{\prime}_{2}(G)\leq 4 for every graph G and asked whether \chi^{\prime}_{k}(G) is bounded by some function of k only. Scott [ 9 ] proved that \chi^{\prime}_{k}(G)\leq 5k^{2}\log k for every graph G , and in turn asked if \chi^{\prime}_{k}(G) is in fact bounded by a linear function of k . This would be the best possible apart from the multiplicative constant, as \chi^{\prime}_{k}(K_{1,k})=k . Such a question was answered affirmatively by Botler, Colucci and Kohayakawa in 2023 [ 4 ] , who proved that \chi^{\prime}_{k}(G)\leq 198k-101 for every graph G , and further conjectured that the constant 198 could be reduced to 1 . Conjecture 1 (Botler–Colucci–Kohayakawa, 2023) . Let k\geq 2 be an integer. There is a constant C such that \chi^{\prime}_{k}(G)\leq k+C for every graph G . In support of Conjecture 1 , Botler, Colucci, and Kohayakawa [ 3 ] proved that for every positive integer k there is a constant C_{k} such that if np\geq C_{k}\log k and n(1-p)\to\infty as n\to\infty , then the following holds asymptotically almost surely: if k is odd, then \chi^{\prime}_{k}(G(n,p))=k , while if k is even, then \chi^{\prime}_{k}(G(2n,p))=k and \chi^{\prime}_{k}(G(2n+1,p))=k+1 . They also observed that the constant C in Conjecture 1 must be at least 2 , since \chi^{\prime}_{k}(K_{1,k,k})=k+2 . Further progress towards verifying Conjecture 1 was made by Nweit and Yang [ 7 ] , who improved the multiplicative constant to 177 , proving that \chi^{\prime}_{k}(G)\leq 177k-93 . In this paper, we further improve this constant as follows. Theorem 2 . There is a function f\in o(k) such that for every positive integer k and every graph G , we have \chi^{\prime}_{k}(G)\leq 9k+f(k) . In addition, if k is odd then \chi^{\prime}_{k}(G)\leq 7k+f(k) . The proof of Theorem 2 follows a general approach [ 4 , 7 , 9 ] that involves removing a maximal colour class – that is, the largest subgraph whose degrees are all congruent to 1\pmod{k} – to reduce the problem to a graph with bounded degeneracy, and then constructing a \chi^{\prime}_{k} -colouring of such graph using few colours. Our improvement builds on two key ingredients. First, we establish a stronger upper bound for the weak Alon–Friedland–Kalai Conjecture (see Conjecture 4 ), which yields a tighter estimate on the number of edges – and consequently, on the degeneracy – of the graph remaining after removing a maximal colour class. Second, we provide an improved upper bound on the mod k chromatic index of graphs with bounded degeneracy. This is our main technical contribution. The Alon–Friedland–Kalai Conjecture. We say that a graph H is k -divisible if d_{H}(u)\equiv 0\pmod{k} for every u\in V(H) . In 1984, Alon, Friedland, and Kalai [ 1 ] explored the extremal problem of calculating the maximum number of edges of a graph on n vertices with no k -divisible subgraph, and proved the following upper bound in the case k is a prime power. Theorem 3 (Alon–Friedland–Kalai, 1984) . Let k be a prime power. If G is a graph on n vertices that does not contain a non-empty k -divisible subgraph, then e(G)\leq(k-1)n . They also conjectured that Theorem 3 can be generalized for any k . Conjecture 4 (Alon–Friedland–Kalai, 1984) . Let k be a positive integer. If G is a graph on n vertices that does not contain a non-empty k -divisible subgraph, then e(G)\leq(k-1)n . Botler, Colucci, and Kohayakawa proved a weaker version of Conjecture 4 in which (k-1)n is replaced by (24k-12)n [ 4 , Lemma 3] . We show that this bound can be sharpened as follows. Throughout the text, given a positive integer k , we denote by q(k) the smallest prime number that is equal to, or greater than k . Lemma 5 . Let k\geq 2 be an integer. If G is an n -vertex graph that does not contain any non-empty k -divisible subgraph, then e(G)\leq(q(\frac{3k}{2})-1)n . Moreover, if k is odd, then e(G)\leq(q(k)-1)n . The proof of Lemma 5 is fairly straightforward and combines a simple idea from [ 5 ] with known results guaranteeing the existence of k -regular subgraphs in r -regular graphs [ 6 , 10 ] . Lemma 6 (Tashkinov, 1982) . Let r and k be positive odd integers with 0<k<r . Then every r -regular

Read the complete text