Odd Cycle Decomposition

An odd cycle decomposition of fixed length is a graph decomposition into cycle graphs , where is odd. Necessary divisibility conditions are that every vertex degree is even and that divides the edge count. A graph satisfying these conditions is called -divisible (Hou et al. 2026).

Hou et al. (2026) proved that, for every fixed odd and every , all sufficiently large -vertex -divisible simple graphs with

have such a decomposition, where is the minimum vertex degree. The coefficient is best possible. Their new cases are , 7, ..., 71, completing the thresholds for all fixed odd lengths. For , this coefficient is .