Given a graph $G$ and an integer $k \geq 2$, let $\chi'_k(G)$ denote the minimum number of colours required to colour the edges of $G$ such that, in each colour class, the subgraph induced by the edges of that colour has all non-zero degrees congruent to $1$ modulo $k$. In 1992, Pyber proved that $\chi'_2(G) \leq 4$ for every graph $G$, and posed the question of whether $\chi'_k(G)$ can be bounded solely in terms of $k$ for every $k \geq 3$. This question was answered in 1997 by Scott, who showed that $\chi'_k(G) \leq 5k^2 \log k$, and further asked whether $\chi'_k(G) = O(k)$. Recently, Botler, Colucci, and Kohayakawa (2023) answered Scott’s question affirmatively, proving that $\chi'_k(G) \leq 198k - 101$, 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 $\chi'_k(G) \leq 177k - 93$.
In this talk, we will discuss the details of how we reduced this multiplicative constant to $9$ and present further open questions concerning modular colouring of graphs.
(Pedro Mariano Viana Neto) [Instituto de Matemática e Estatística, São Paulo]
Vérifiez que vous êtes bien inscrits sur le site du [gdr-ifm-gt-graphes] : [ https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres | https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres ]
Remarks / Remarques
Find all the information of the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] .
Retrouvez toutes les informations du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .