Colorações de grafos módulo k

• Processo: 25/13056-1
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de agosto de 2025
• Data de Término da vigência: 31 de julho de 2026
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Fábio Happ Botler
• Beneficiário: Pedro Mariano Viana Neto
• Instituição Sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
• Vinculado ao auxílio: 24/14906-6 - Partições e Coberturas de grafos, AP.R
• Bolsa(s) vinculada(s): 25/24104-7 - Índice cromático mod k, BE.EP.IC
• Assunto(s): Teoria dos grafos
• Palavra(s)-Chave do Pesquisador: Coloração de arestas | grafo | linear | módulo k | Teoria dos Grafos

Resumo

Dado inteiro positivo k, dizemos que um grafo G é ímpar módulo k se todo vértice de G tem grau congruente a 1 módulo k, e denotamos por X_k'(G) a cardinalidade da menor coloração de G na qual cada cor induz um grafo ímpar módulo k, que chamamos de índice cromático módulo k. Este problema foi inicialmente proposto em 1992 por Pyber, que provou que X'_2(G) é no máximo 4. Em 1997, Scott provou que X_k'(G) é no máximo 5 k^2 log k, e perguntou se tal limitante não é de fato linear. Recentemente, em colaboração com Lucas Colucci e Yoshiharu Kohayakawa, da Universidade de São Paulo, respondemos afirmativamente à pergunta de Scott, mostrando que X_k'(G) é no máximo 198k, para todo k. Neste projeto, planejamos reduzir a constante 198 acima.