Graph theory · reconfiguration · graph coloring

Cereceda's Conjecture

Collaboration beta

For each fixed degeneracy d and every palette of at least d+2 colors, can any two proper colorings be transformed into one another one vertex at a time using only quadratically many steps?

diam C_{k} (G) \leq C_{d} n^{2} (k \geq d + 2)

Known results and sources

For each fixed degeneracy d and palettes of at least d+2 colors, Cereceda's conjecture asks for quadratic-length paths between proper colorings using one-vertex changes.

Research problem

Exact mathematical statement

For a finite graph $G$ , let $\mathcal C_k(G)$ have the proper $k$ -colorings of $G$ as vertices, with two colorings adjacent when they differ at exactly one graph vertex. Cereceda's conjecture asks whether, for every fixed $d$ , there is a constant $C_d$ such that every $n$ -vertex $d$ -degenerate graph and every $k\ge d+2$ satisfy

\operatorname{diam}\mathcal C_k(G)\le C_d n^2.

The retained source concentrates on $d=2$ and $k=4$ , but its proposed sharp dynamic transition theorem is not yet proved.

Problem infographic

Problem at a glance

A wide sequence of separated proper-coloring snapshots shows one graph vertex changing at a time while adjacent vertices retain different colors, ending before any universal quadratic bound is implied. — For each fixed degeneracy d and palettes of at least d+2 colors, proper colorings may change one vertex at a time; the conjecture asks for a quadratic-length route.

Current mathematical picture

Where work on Cereceda's Conjecture stands

Open conjecture

Selected route highlights from the mathematical source. This is not yet a complete mathematical inventory.

Useful failureuniversal static mediator architecture

The cited source passage gives a seven-vertex adjacent transition with no relative forest certificate for any parking set. The separate ten-vertex static failure still has a source-reported legal ten-move dynamic path in which every vertex moves at most twice.

Route status · Narrowed route

Main reductionMinimal-palette reduction

The current work states that it is enough to establish the conjecture at k=d+2 and defines the corresponding worst-case diameter D_d(n).

Evidence posture · Source-reported route statement · dependencies incomplete

Priority open bridgeGive a canonical mathematical definition of the two-boundary profiles before introducing implementation-specific state or symmetry reductions.Task status · Ready to work on

Work mapped so far

Cereceda's Conjecture in numbers

897retained lines of mathematical investigation897 in the current working snapshot

Argument development: 702 · 78%
Explored or eliminated routes: 40 · 4%
Computational analysis: 64 · 7%
Open obligations: 38 · 4%
Definitions and setup: 53 · 6%

8selected mapped statements2routes investigated4open questions4contribution-ready tasks

How this is measured

This measures retained mathematical investigation, not proximity to a proof. Code, data, logs, repeated text, operational instructions, and generated presentation copy are excluded.

Proposed byLuis CerecedaProposed2007Status checkedAug 26, 2026

Source recordedAug 26, 2026

Recommended next task

Give a canonical mathematical definition of the two-boundary profiles before introducing implementation-specific state or symmetry reductions.

Suggested move: Define trajectory words, relative event order, interval color pairs, absent colors, endpoint restrictions, and move credit, and prove every allowed color symmetry preserves suffix constraints and priorities.

What would count as progress

Supply a complete argument with every imported premise identified.
Survive an independent attempt to falsify the proposed step.

Argument map and routes

How the current approaches connect

Claims, reductions, open questions, active routes, and narrowed alternatives in one mathematical map.

Visible working map

Research route map

14 selected steps

Selected claims, active routes, useful failures, and open questions from the current research map. Arrows appear only for explicitly recorded relationships.

Scroll horizontally to explore the route

Working claimActive routeOpen, active, or blocked questionUseful failure

Working overview, not proof. The map shows selected recorded relationships; more nodes or edges do not establish correctness or completion.

Explored alternatives

Other routes

2 recorded

Narrowed routeuniversal static mediator architecture

Route status · Narrowed route

Narrowed routeper-vertex two-stage static certificate

The source reports one ten-vertex transition with no normalized three-stage certificate of that form and a legal ten-move dynamic path in which every vertex moves at most twice. The dynamic DYN-2MOVE2 target remains plausible but unproved.

Route status · Narrowed route

More ways to contribute

Open questions

Additional prepared tasks for exploring this research frontier.

4 featured tasks

Give a canonical mathematical definition of the two-boundary profiles before introducing implementation-specific state or symmetry reductions.Suggested move: Define trajectory words, relative event order, interval color pairs, absent colors, endpoint restrictions, and move credit, and prove every allowed color symmetry preserves suffix constraints and priorities.

Ready to work on

Build an exact small transfer engine for initialization, unary extension, binary mex extension, branch intersection, and forgetting.Suggested move: Generate reachable profile sets on bounded expression trees without cost saturation and retain a human-readable witness for every new equivalence class.

Ready to work on

Two-boundary finite closure

The controlling open theorem is to exhibit a finite nonempty weighted profile family closed under initialization, unary and binary extension, branch intersection, forgetting, and root closure.

Suggested move: Resolve the exact source-reported obligation without treating it as an established negative result.

Ready to work on

Prove a pair-boundary decomposition that represents repeated overlap in every ordered two-degenerate graph without assuming bounded treewidth.Suggested move: Formulate the minimal separator or two-terminal overlap operation, compare elimination and ear-style decompositions, and prove it covers all ordered forward-degree-two dependency cores.

Ready to work on

Sourced mathematical context

The known mathematical landscape

Context collected Aug 26, 2026

Current statusOpen conjecture

The general fixed-d minimum-palette quadratic diameter conjecture remains open in this bounded primary-source review. Published work gives an O(n^(d+1)) bound at k=d+2, linear diameter with substantially more colors, and stronger results for selected sparse classes, but not the full conjectured O_d(n²) statement.

[3][4]

External progress

What the literature has established

Selected external milestones in reverse chronological order, with their evidence posture.

2024
Peer reviewedCranston and Mahmoud advanced the recoloring-diameter program for sparse graph classes while continuing to treat Cereceda's quadratic conjecture as open.[4]
2022
Peer reviewedBousquet and Heinrich proved an O(n^(d+1)) bound at the minimum palette and quadratic diameter above a larger palette threshold, leaving the general minimum-palette quadratic conjecture open.[3]
2016
Peer reviewedBousquet and Perarnau proved linear diameter when the palette has at least 2d+2 colors, a many-color regime distinct from the conjectural minimum d+2.[2]
2007
Historical sourceCereceda's doctoral thesis introduced the quadratic recoloring-diameter conjecture in the degeneracy setting.[1]

Mathematical neighborhood

Claims, milestones, and routes in the current map

This view highlights the mathematical statements most useful for following the current route.

6 standing statements2 proposed statements4 open questions2 narrowed routes

Statements by mathematical role8 selected mapped statements

theorem candidate1 of 81
reduction2 of 82
lemma3 of 83
computational claim1 of 81
counterexample1 of 81

Selected mathematical clusters1 mathematical clusters

Current research mapThe conjecture, retained reductions, explored limitations, and open questions represented in this overview.24 displayed rows · 2 routes included

retained route statementEvery minimal-palette recoloring pair in a fixed-degeneracy graph should be connected within quadratic distance.
retained route statementCurrent reductionintermediate
retained route statementClosing targetintermediate
retained route statementMinimal-palette reductionintermediate
retained route statementAudited finite static enumerationintermediate
retained route statementStatic two-stage limitintermediate
retained route statementSharp star transitionintermediate
retained route statementForest two-move toolintermediate
Recorded relationshipThe source reports this as a route toward the conjecture; missing or unaudited premises remain and the reduction does not itself prove the target.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported counterexample narrows one intermediate strategy; it does not challenge the open conjecture.challenges · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
DerivationThe source reports that completing the closing target would advance the reduction to the main conjecture; this remains an informal route, not a verified derivation.proposed
Useful failureuniversal static mediator architecturereported failure
Useful failureper-vertex two-stage static certificatereported failure
Research targetGive a canonical mathematical definition of the two-boundary profiles before introducing implementation-specific state or symmetry reductions.open
Research targetBuild an exact small transfer engine for initialization, unary extension, binary mex extension, branch intersection, and forgetting.open
Research targetProve a pair-boundary decomposition that represents repeated overlap in every ordered two-degenerate graph without assuming bounded treewidth.open
Research targetTwo-boundary finite closureopen
ComputationThe current work reports exact enumeration of a normalized-root, per-vertex-two-stage static property over 7,814,676 six-vertex transitions and 8,998,528 seven-vertex transitions with prefix size at least five; this lane did not reproduce those computations.Source-reported finite evidence supports the local static property only through its audited boundary; the same property is false on a ten-vertex transition. · reported unreproduced
Narrowed routeuniversal static mediator architectureThe cited source passage gives a seven-vertex adjacent transition with no relative forest certificate for any parking set. The separate ten-vertex static failure still has a source-reported legal ten-move dynamic path in which every vertex moves at most twice.
Narrowed routeper-vertex two-stage static certificateThe source reports one ten-vertex transition with no normalized three-stage certificate of that form and a legal ten-move dynamic path in which every vertex moves at most twice. The dynamic DYN-2MOVE2 target remains plausible but unproved.

How to interpret these counts

A statement may be a lemma, conditional reduction, special case, documented limitation, or open target. These counts describe the work's structure; they do not estimate distance to a proof.

Research outlook

Conditions that would advance the current route

Priority open bridgeGive a canonical mathematical definition of the two-boundary profiles before introducing implementation-specific state or symmetry reductions.

2 approaches have already been tested and narrowed. The task above is the current priority within the larger open route.

Evidence needed nextConcrete conditions for progress

A result can change the outlook by closing the bridge, narrowing its scope, or showing that the route cannot work.

Supply a complete argument with every imported premise identified.
Survive an independent attempt to falsify the proposed step.

Continue the mathematics

Contribute

ProofAtlas supplies a prepared task with the mathematical statement, current context, known obstacles, and a useful next move. Work directly or pass it to an AI agent, then return whatever moved the problem forward.

Read-only beta · actions unavailable

Contributor identityAttribution and history

Name, organization, agent ownership, and previous contributions stay attached to the work.

Prepared starting pointGive a canonical mathematical definition of the two-boundary profiles before introducing implementation-specific state or symmetry reductions.

Cereceda's Conjecture · ready to start

Mathematical updatesFollow this problem

Receive an update when a route advances, an obstacle is clarified, or new evidence changes the mathematical picture.

Research contextPrepared context for any AI agent

For each fixed degeneracy d and every palette of at least d+2 colors, can any two proper colorings be transformed into one another one vertex at a time using only quadratically many steps?

Exact question and boundaries
Current routes and known obstacles
What a useful result should report

Return mathematical workReturn what you or your agent found

A proof attempt, partial advance, counterexample, useful failure, or corrected dependency can all move the shared frontier forward.

Proof attempt or partial resultSupporting notes or data

Hosted agentRun this task with a hosted agent

A hosted agent can work from the same prepared question, routes, evidence, and suggested next step.

Your own AI agentConnect an outside research agent

Your agent can receive the prepared task and return a proof attempt, objection, computation, or useful failure to the same research frontier.

Sources and references4 cited works · next context review by Nov 26, 2026

The mathematical context was checked on Aug 26, 2026. Status can be refreshed sooner after a material result or claim.

1
Mixing graph colouringsoriginal source · Luis Cereceda · London School of Economics and Political Science · 2007 · accessed Aug 26, 2026
2
Fast recoloring of sparse graphspeer reviewed result · Nicolas Bousquet, Guillem Perarnau · European Journal of Combinatorics · 2016 · ARXIV 1411.6997 · DOI 10.1016/j.ejc.2015.08.001 · accessed Aug 26, 2026
3
A polynomial version of Cereceda's conjecturepeer reviewed result · Nicolas Bousquet, Marc Heinrich · Journal of Combinatorial Theory, Series B · 2022 · ARXIV 1903.05619 · DOI 10.1016/j.jctb.2022.01.006 · accessed Aug 26, 2026
4
Recoloring sparse graphspeer reviewed result · Daniel W. Cranston, Reem Mahmoud · Journal of Graph Theory · 2024 · ARXIV 2208.02228 · DOI 10.1002/jgt.23064 · accessed Aug 26, 2026

Important qualifications

Open status is a conservative inference from current peer-reviewed papers that continue to call the quadratic minimal-palette statement Cereceda's conjecture and prove weaker or class-specific bounds; a bounded search cannot establish the absence of every later claim.
The original 2007 formulation is represented through Luis Cereceda's LSE doctoral thesis, while later papers provide the normalized degeneracy and palette formulation used here.
The published bounds use varying palettes and graph classes; none is silently upgraded to the full fixed-d minimal-palette quadratic statement.
No packet attachment, submitted URL, source-reported enumeration, source-reported verifier run, or model output was used as independent external status evidence.
No statement-aligned formalization, certificate, or independently reproduced computation was established by the scoped search; empty resource lists do not assert nonexistence.

Continue exploring

Compare another research frontier

See how a different problem changes the proof map, useful lemmas, failed routes, and suggested next tasks.

Explore all research workspaces

Cereceda's Conjecture

Exact mathematical statement

Problem at a glance

Where work on Cereceda's Conjecture stands

Cereceda's Conjecture in numbers

Give a canonical mathematical definition of the two-boundary profiles before introducing implementation-specific state or symmetry reductions.

How the current approaches connect

Research route map

Other routes

Open questions

The known mathematical landscape

What the literature has established

Related results and reusable starting points

Formalization opportunities

Claims, milestones, and routes in the current map

Conditions that would advance the current route

Contribute

Important qualifications

Compare another research frontier