On mod k chromatic index

• Grant number: 25/24104-7
• Support Opportunities: Scholarships abroad - Research Internship - Scientific Initiation
• Start date: February 28, 2026
• End date: June 27, 2026
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Fábio Happ Botler
• Grantee: Pedro Mariano Viana Neto
• Supervisor: Marthe Armande Adele Bonamy
• Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil
• Institution abroad: Université Bordeaux 1, France
• Associated to the scholarship: 25/13056-1 - Mod k colorings of graphs, BP.IC

Abstract

Let chi_k'(G) be the minimum number of colors needed to color the edges of a graph such that each color spans a subgraph with the property that the degree of all vertices is congruent to 1 modulo k. In 1992, Pyber proved that chi_2'(G) <= 4 for every graph G and asked whether chi_k'(G) could be bounded by a function of k for k >= 3. This question was further answered in 1997 by Scott, who showed chi_k'(G) <= 5k^2 log(k) and asked whether chi_k'(G) = O(k). Recently in 2023, Botler, Colucci and Kohayakawa answered affirmatively to Scott's question, proving chi_k'(G) <= 198k - 101, and conjectured that the multiplicative constant could be reduced to 1. In 2024, Nweit and Yang improved this bound to chi_k'(G) <= 177k - 93. Another step was made in 2025 by Berthe, Bonamy, Botler, Carenini, Colucci, Dumas, Ghasemi and Mariano Viana Neto, who reduced the multiplicative constant to 9. More specifically, we proved that there is a function f in o(k) such that chi_k'(G) <= 7k + f(k), if k is odd and chi_k'(G) <= 9k + f(k) if k is even. The idea of this project is to strengthen this collaboration, improving the constant bound for chi_k'(G), and investigate some variants of the original problem, such as weak mod k edge colorings.