Erdős–Gyárfás cycle conjecture

Open

erdos-gyarfas-cycles

Statement

Prove that every graph with minimum degree at least

3

contains a cycle whose length is a power of

2

— or exhibit a min-degree-

3

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

3

in particular.

When this counts as solved

BINARY. PROOF_COMPLETE for the general statement, or COUNTEREXAMPLE: an explicit min-degree-

3

graph with no power-of-two cycle. Liu–Montgomery already cover large minimum degree, so re-deriving that is not terminal.

Classification

binary

Mine this problem →