Decomposing a complete graph to avoid small odd cycles
Home
Search
Subjects
About Erdös
About This Site
Search
Subjects
- All (170)
- Ramsey Theory (40)
- Extremal Graph Theory (40)
- Coloring, Packing, and Covering (25)
- Random Graphs and Graph Enumeration (16)
- Hypergraphs (35)
- Infinite Graphs (14)
About Erdös
About This Site
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.