Decomposing a complete graph to avoid small odd cycles

It is known that a complete graph on \(2^n\) vertices can be edge-partitioned into \(n\) bipartite graphs (and this is not true for \(2^n+1\)). Suppose a complete graph on \(2^n+1\) vertices is decomposed into \(n\) subgraphs. Let \(f(n)\) denote the smallest integer \(m\) such that one of the subgraphs must contain an odd cycle of length less than or equal to \(m\).

Problem (proposed by Erdös and Graham [1])

Determine \(f(n)\).

Problem (proposed by Erdös and Graham [1])

Is \(f(n)\) unbounded as \(n \rightarrow \infty\)?

Although this is a fairly old problem, relatively little is known. It can be easily shown that \( C_5\) and \( C_7\) can be avoided provided \( n\) is large.

1 P. Erdös and R. L. Graham, On partition theorems for finite graphs, Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdös on his 60th birthday), Vol. I; Colloq. Math. Soc. János Bolyai, Vol. 10, 515-527, North-Holland, Amsterdam, 1975.