EUVIMEDEUVIMED entdecken
Crossref

On Modular Edge Colorings of Graphs

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

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →