---
tag: APHZQSY2DK
kind: statement
role: proposition
name: Cereceda's conjecture
sources:
  - wikipedia: en:62405866@r1349175963
    locator: Cereceda's conjecture
    note: adopted
    mention: wikipedia://en/62405866
    sections: [Statement]
same_as:
  wikidata: Q85751315
  wikipedia: Cereceda's conjecture
inventory: [EKBA6DEFEH]
---

## Statement

In the mathematics of [[graph coloring|0NCPXH194Y]], **Cereceda’s conjecture** is an unsolved problem on the distance between pairs of colorings of sparse graphs. It states that, for two different colorings of a graph of degeneracy $d$, both using at most $d + 2$ colors, it should be possible to reconfigure one coloring into the other by changing the color of one vertex at a time, using a number of steps that is quadratic in the size of the graph. The conjecture is named after Luis Cereceda, who formulated it in his 2007 doctoral dissertation.