Modular Graph Colourings

Add to your list(s) Download to your calendar using vCal

• Gaia Carenini (Cambridge)
• Thursday 30 October 2025, 14:30-15:30
• MR12.

If you have a question about this talk, please contact ibl10.

Given a graph G and an integer k ≥ 2, let χ′ₖ(G) denote the minimum number of colours required to colour the edges of G so 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 χ′₂(G) ≤ 4 for every graph G and asked whether χ′ₖ(G) can be bounded solely in terms of k for every k ≥ 3. This question was answered in 1997 by Scott, who showed that χ′ₖ(G) ≤ 5k² log k, and further asked whether χ′ₖ(G) grows only linearly with k. Recently, Botler, Colucci, and Kohayakawa (2023) answered Scott’s question affirmatively, proving that χ′ₖ(G) ≤ 198k − 101, and conjectured that the multiplicative constant could be reduced to 1. A step toward this conjecture was made in 2024 by Nweit and Yang, who improved the bound to χ′ₖ(G) ≤ 177k − 93.In this work, we further improve the multiplicative constant to 9. More specifically, we show that χ′ₖ(G) ≤ 7k o(k) when k is odd, and χ′ₖ(G) ≤ 9k o(k) when k is even. As part of our proof, we establish that χ′ₖ(G) ≤ k + O(d) for every d-degenerate graph G, a result that plays a central role in our argument.

This talk is part of the Combinatorics Seminar series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• Combinatorics Seminar
• DPMMS Lists
• DPMMS Pure Maths Seminar
• DPMMS info aggregator
• DPMMS lists
• Hanchen DaDaDash
• Interested Talks
• MR12
• School of Physical Sciences
• bld31

Note that ex-directory lists are not shown.