On Modular Edge Colorings of Graphs
SIAM Journal on Discrete Mathematics · 30.06.2026 · 40 (2) · 897-904
DOI: 10.1137/25m1775488 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Discrete Mathematics, online erschienen am 04.06.2026. Verfasst von Gaétan Berthe und 7 weiteren Autor:innen. Die Arbeit nennt 18 Literaturangaben. Gefördert von: Coordenação de Aperfeiçoamento de Pessoal de Nível Superior, Conselho Nacional de Desenvolvimento Científico e Tecnológico, Fundação de Amparo à Pesquisa do Estado de São Paulo.
Abstract (Originalsprache)
Given a graph [Formula: see text] and an integer [Formula: see text], let [Formula: see text] denote the minimum number of colors required to color the edges of [Formula: see text] such that, in each color class, the subgraph induced by the edges of that color has all nonzero degrees congruent to 1 modulo [Formula: see text]. In 1992, Pyber proved that [Formula: see text] for every graph [Formula: see text], and posed the question of whether [Formula: see text] can be bounded solely in terms of [Formula: see text] for every [Formula: see text]. This question was answered in 1997 by Scott, who showed that [Formula: see text], and further asked whether [Formula: see text]. Recently, Botler, Colucci, and Kohayakawa (2023) answered Scott’s question affirmatively proving that [Formula: see text], and conjectured that the multiplicative constant could be reduced to 1. A step towards this latter conjecture was made in 2024 by Nweit and Yang, who improved the bound to [Formula: see text]. In this paper, we further improve the multiplicative constant to 9. More specifically, we prove that there is a function [Formula: see text] for which [Formula: see text] if [Formula: see text] is odd, and [Formula: see text] if [Formula: see text] is even. In doing so, we prove that [Formula: see text] for every [Formula: see text]-degenerate graph [Formula: see text], which plays a central role in our proof.
Förderung
- Coordenação de Aperfeiçoamento de Pessoal de Nível Superior
- Conselho Nacional de Desenvolvimento Científico e Tecnológico
- Fundação de Amparo à Pesquisa do Estado de São Paulo
- Trinity College, University of Cambridge
- Bahia Research Foundation
- Agence Nationale de la Recherche
- IUT Senart-Fontainebleau
Zitieren
APA
Berthe, G., Bonamy, M., Botler, F., Carenini, G., Colucci, L., Dumas, A., Ghasemi, F., & Neto, P. M. V. (2026). On Modular Edge Colorings of Graphs. SIAM Journal on Discrete Mathematics, 40(2), 897-904. https://doi.org/10.1137/25m1775488
Vancouver
Berthe G, Bonamy M, Botler F, Carenini G, Colucci L, Dumas A, et al. On Modular Edge Colorings of Graphs. SIAM Journal on Discrete Mathematics. 2026;40(2):897-904. doi:10.1137/25m1775488
BibTeX
@article{Berthe2026,
author = {Berthe, Gaétan and Bonamy, Marthe and Botler, Fábio and Carenini, Gaia and Colucci, Lucas and Dumas, Arthur and Ghasemi, Fatemeh and Neto, Pedro Mariano Viana},
title = {On Modular Edge Colorings of Graphs},
journal = {SIAM Journal on Discrete Mathematics},
year = {2026},
volume = {40},
number = {2},
pages = {897--904},
doi = {10.1137/25m1775488}
}
EUVIMED