← All problems
Erdős–Gyárfás cycle conjecture
Openerdos-gyarfas-cycles
Statement
Prove that every graph with minimum degree at least contains a cycle whose length is a power of — or exhibit a min-degree- graph with no such cycle.
Current frontier
erdosproblems.com/64, OPEN. Liu–Montgomery (2020) settled all sufficiently large minimum degree (and disproved the stronger Erdős–Gyárfás conjecture); the open content is the small-degree regime, minimum degree in particular.
When this counts as solved
BINARY
PROOF_COMPLETE for the general statement, or COUNTEREXAMPLE: an explicit min-degree- graph with no power-of-two cycle. Liu–Montgomery already cover large minimum degree, so re-deriving that is not terminal.
Classification
Binary