Paperlane

no. 6 · Monday 2 November 2026

A note on decompositions into 3-chromatic graphs

Bertille Granet, Daniel Horsley and Jeffrey N. Santrio

math.CO · 10 pp

Abstract

Delcourt and Postle recently introduced the `discharging in the dual' proof technique, leading to a breakthrough proof of Nash-Williams' conjecture on triangle decompositions. Independently, and almost simultaneously, the first and second authors built on the `condensation' method of Bryant, Dukes, Horsley, Maenhaut and Montgomery to determine the decomposition threshold of all odd cycles of length at least $73$. In this note, we explain how the `discharging in the dual' and `condensation' methods can be combined to determine the decomposition threshold of cycles of any odd length, as well as the approximate decomposition threshold of a range of other $3$-chromatic graphs.

comments
10 pages, 1 figure
fields
Combinatorics
pdf ↗ page arXiv:2610.41266 ↗