Mod k colorings of graphs

• Grant number: 25/13056-1
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: August 01, 2025
• End date: July 31, 2026
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Fábio Happ Botler
• Grantee: Pedro Mariano Viana Neto
• Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil
• Associated research grant: 24/14906-6 - Partitioning and Covering of Graphs, AP.R

Abstract

Given a positive integer k, we say that a graph G is odd modulo k if every vertex in G has degree equal to 1 modulo k. We write X_k'(G) for the smallest number of colors needed to color the edges of G so that each color class forms an odd modulo k graph. This number is called the modulo k chromatic index. The problem was first proposed in 1992 by Pyber, who showed that X'_2(G) is at most 4. In 1997, Scott proved that X_k'(G) is at most 5k^2log k, and asked whether this upper bound could actually be linear. Recently, in collaboration with Lucas Colucci and Yoshiharu Kohayakawa from the University of São Paulo, we answered Scott's question positively by showing that X_k'(G) is at most 198k, for all values of k. In this project, we plan to improve this result by reducing the constant 198.