Monochromatic Odd Cycles in Edge-Colored Complete Graphs
It is easy to see that every [Formula: see text]-edge-coloring of the complete graph on [Formula: see text] vertices must contain a monochromatic odd cycle. A natural question raised by Erdős and Graham in 1973 asks for the smallest [Formula: see text] such that every [Formula: see text]-edge-coloring of [Formula: see text] must contain a monochromatic odd cycle of length at most [Formula: see text]. In here, we show that [Formula: see text] giving the first nontrivial upper bound on [Formula: see text].
Authors
- Zach Hunter
- António Girão (ORCID: https://orcid.org/0000-0002-1206-7128)
Institutions
- ETH Zurich (CH)
- University of Oxford (GB)
Publication Details
- Journal
- SIAM Journal on Discrete Mathematics
- Published
- 2026-11-18
- DOI
- https://doi.org/10.1137/25m1807575
- Citations
- 6
- Primary Topic
- Limits and Structures in Graph Theory
- Type
- article
- Field-Weighted Citation Impact
- 7.32